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

import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

public classPriorityQueue<Key> implements Iterable<Key> {
private Key[] pq;   
private int n;   
private Comparator<Key> comparator;
publicPriorityQueue(int initCapacity) {
pq = (Key[]) new Object[initCapacity + 1];
n = 0;
}

publicPriorityQueue() {
this(1);
}
publicPriorityQueue(int initCapacity, Comparator<Key> comparator) {
this.comparator = comparator;
pq = (Key[]) new Object[initCapacity + 1];
n = 0;
}
publicPriorityQueue(Comparator<Key> comparator) {
this(1, comparator);
}

publicPriorityQueue(Key[] keys) {
n = keys.length;
pq = (Key[]) new Object[keys.length + 1];
for (int i = 0; i < n; i++)
pq[i+1] = keys[i];
for (int k = n/2; k >= 1; k--)
sink(k);
assert isMaxHeap();
}
  

public boolean isEmpty() {
return n == 0;
}

public int size() {
return n;
}

public Key max() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
return pq[1];
}

private void resize(int capacity) {
assert capacity > n;
Key[] temp = (Key[]) new Object[capacity];
for (int i = 1; i <= n; i++) {
temp[i] = pq[i];
}
pq = temp;
}

public void insert(Key x) {

// double size of array if necessary
if (n >= pq.length - 1) resize(2 * pq.length);

pq[++n] = x;
swim(n);
assert isMaxHeap();
}
public Key delMax() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
Key max = pq[1];
exch(1, n--);
sink(1);
pq[n+1] = null; // to avoid loiterig and help with garbage collection
if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2);
assert isMaxHeap();
return max;
}

private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}

private void sink(int k) {
while (2*k <= n) {
int j = 2*k;
if (j < n && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
private boolean less(int i, int j) {
if (comparator == null) {
return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
}
else {
return comparator.compare(pq[i], pq[j]) < 0;
}
}

private void exch(int i, int j) {
Key swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
}

private boolean isMaxHeap() {
return isMaxHeap(1);
}

private boolean isMaxHeap(int k) {
if (k > n) return true;
int left = 2*k;
int right = 2*k + 1;
if (left <= n && less(k, left)) return false;
if (right <= n && less(k, right)) return false;
return isMaxHeap(left) && isMaxHeap(right);
}

public Iterator<Key> iterator() {
return new HeapIterator();
}

private class HeapIterator implements Iterator<Key> {

privatePriorityQueue<Key> copy;
public HeapIterator() {
if (comparator == null) copy = newPriorityQueue<Key>(size());
else copy = newPriorityQueue<Key>(size(), comparator);
for (int i = 1; i <= n; i++)
copy.insert(pq[i]);
}

public boolean hasNext() { return !copy.isEmpty(); }
public void remove() { throw new UnsupportedOperationException(); }

public Key next() {
if (!hasNext()) throw new NoSuchElementException();
return copy.delMax();
}
}

public static void main(String[] args) {
PriorityQueue<String> pq = newPriorityQueue<String>();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) pq.insert(item);
else if (!pq.isEmpty()) StdOut.print(pq.delMax() + " ");
}
StdOut.println("(" + pq.size() + " left on pq)");
}

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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