The goal of the homework is to implement a priority queue as a BST adapter. Belo

Question

The goal of the homework is to implement a priority queue as a BST adapter.

Below are the package that has been imported above, dont change them just give me the code required for insert and removemin where it says TODO and dnt change anything please

-------------------------------------------------------

-----------------------------------------------------------

---------------------------------

....................................................................................................................................

-----------------------------------------

package class13;

import java.util.ArrayList;
import class12.Tree;

public class BinaryTree extends Tree {
public BinaryTree() {
super();
}

public void addRoot(T x) throws Exception {
if (root != null) throw new Exception("The tree is not empty");
root = new BNode(x, null, null, null);
size++;
}

public void addLeft(BNode n, T x) throws Exception {
if (n.getLeft() != null) throw new Exception("Already used");
n.setLeft(new BNode(x, n, null, null));
size++;
}

public void addRight(BNode n, T x) throws Exception {
if (n.getRight() != null) throw new Exception("Already used");
n.setRight(new BNode(x, n, null, null));
size++;
}

// returns the parent of the removed node
public BNode removeNode(BNode n) {
if (isLeaf(n)) { // base case
BNode p = (BNode) parent(n);
if (p == null) root = null;
else p.removeChild(n);
size--;
return p;
}
if (n.getLeft() != null) {
BNode m = rightmostLeftDescendant(n);
n.setData(m.getData());
return removeNode(m); // recursively remove rightmost left descendant
}
// otherwise n does have a right child
BNode m = leftmostRightDescendant(n);
n.setData(m.getData());
return removeNode(m);
}

public BNode leftmostRightDescendant(BNode n) {
BNode m = n.getRight();
while (m.getLeft() != null) m = m.getLeft();
return m;
}

public BNode rightmostLeftDescendant(BNode n) {
BNode m = n.getLeft();
while (m.getRight() != null) m = m.getRight();
return m;
}

public ArrayList> inOrder() {
ArrayList> answer = new ArrayList>();
inOrder((BNode) root(), answer);
return answer;
}

public void inOrder(BNode n, ArrayList> v) {
if (n == null) return;
inOrder(n.getLeft(), v);
v.add(n);
inOrder(n.getRight(), v);
}

public ArrayList> flatOrder() {
return inOrder();
}
}

-------------------------------

package class22;

public interface BSTree> {

   public void remove(K x);

   public void insert(K x) throws Exception;

   public boolean find(K x);

}

-------------------------------------------------------------------

package class12;

import java.util.ArrayList;
import java.util.Iterator;

public class Tree<T> {
protected Node<T> root;
protected int size;

public Tree() {
root = null;
size = 0;
}

public Node<T> root() {
return root;
}

public Node<T> parent(Node<T> v) {
return v.getParent();
}

public Iterator<? extends Node<T>> children(Node<T> v) {
return v.children();
}

public boolean isRoot(Node<T> v) {
return v == root;
}

public boolean isInternal(Node<T> v) {
return children(v).hasNext();
}

public boolean isLeaf(Node<T> v) {
return !isInternal(v);
}

public int size() {
return size;
}

public boolean empty() {
return size == 0;
}

public void replace(Node<T> v, T t) {
v.setData(t);
}

public int depth(Node<T> v) {
if (isRoot(v))
return 0;
return 1 + depth(parent(v));
}

public int height(Node<T> v) {
if (isLeaf(v))
return 0;
int maxChild = 0;
Iterator<? extends Node<T>> c = children(v);
while (c.hasNext()) {
int hc = height((Node<T>) c.next());
if (hc > maxChild)
maxChild = hc;
}
return maxChild + 1;
}

public int height() {
if (root == null)
return -1;
return height(root);
}

public ArrayList<Node<T>> preOrder() {
ArrayList<Node<T>> answer = new ArrayList<>();
preOrder(root(), answer);
return answer;
}

public void preOrder(Node<T> n, ArrayList<Node<T>> v) {
if (n == null)
return;
v.add(n);
Iterator<? extends Node<T>> x = children(n);
while (x.hasNext()) {
Node<T> m = x.next();
preOrder(m, v);
}
}

public ArrayList<Node<T>> postOrder() {
ArrayList<Node<T>> answer = new ArrayList<Node<T>>();
postOrder(root(), answer);
return answer;
}

public void postOrder(Node<T> n, ArrayList<Node<T>> v) {
if (n == null)
return;
Iterator<? extends Node<T>> x = children(n);
while (x.hasNext()) {
Node<T> m = x.next();
postOrder(m, v);
}
v.add(n);
}

public ArrayList<Node<T>> levelOrder() {
ArrayList<Node<T>> waiting = new ArrayList<>();
waiting.add(null);
if (root() == null)
return waiting;
waiting.add(root());
int done = 0;
while (done < waiting.size()) {
Node<T> oldNode = waiting.get(done++);
if (oldNode == null) {
if (done < waiting.size())
waiting.add(null);
continue;
}
Iterator<? extends Node<T>> c = children(oldNode);
while (c.hasNext())
waiting.add(c.next());
}
return waiting;
}

public ArrayList<? extends Node<T>> flatOrder() {
return preOrder();
}

public String toString() {
return treePrint(null);
}

public String treePrint(Node<T> cursor) {
String answer = " ";
Iterator<Node<T>> lev = levelOrder().iterator();
Iterator<? extends Node<T>> flat = flatOrder().iterator();
lev.next(); // skip first new line
while (lev.hasNext()) {
Node<T> o = lev.next();
if (o == null) {
answer += " ";
flat = flatOrder().iterator();
} else
while (true) {
boolean atCursor = false;
Node<T> n = flat.next();
if (n == cursor)
atCursor = true;
String s = n.getData().toString();
if (atCursor)
s = "* " + s + " *";
if (n == o) {
answer += s;
break;
} else
for (int i = 0; i < s.length(); i++)
answer += ' ';
}
}
return answer;
}
}

Explanation / Answer

I am providing you the pseudo code, hope it helps :

insert :

// First insert the new key at the end
heap_size++;
int i = heap_size - 1;
harr[i] = x;

// Fix the min heap property if it is violated
while (i != 0 && harr[parent(i)] > harr[i])
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}

int parent(int i) { return (i-1)/2; }

void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}

removeMin() :

if (heap_size <= 0)
return INT_MAX;
if (heap_size == 1)
{
heap_size--;
return harr[0];
}

// Store the minimum value, and remove it from heap
int root = harr[0];
harr[0] = harr[heap_size-1];
heap_size--;
MinHeapify(0);

return root;

void MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}

int left(int i) { return (2*i + 1); }

int right(int i) { return (2*i + 2); }

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.