JAVA // Trying to implement BinaryHeap PQ, max-Oriented , need help with swim, sink and delMax functions, using Node ;

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

import stdlib.StdIn; import stdlib.StdOut;

/** * The PtrHeap class is the priorityQ class from Question 2.4.24. * It represents a priority queue of generic keys. * * It supports the usual insert and delete-the-maximum * operations, along with methods for peeking at the maximum key, * testing if the priority queue is empty, and iterating through * the keys. * For additional documentation, see Section 2.4 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. */

public class PtrHeap> { static class Node { K value; Node parent; Node lchild; //leftNode Node rchild; //rightNode } private int size; private Node root; private K[] pq; //2nd question professor can we make a private field for pq because otherwise I cannot see another way; boolean isRoot(Node n){ return n == root; } //isnt isRoot same as max? Node find(int n){ return null; } void exch(Node n1, Node n2) { // only swap items of nodes //difference being only swapping items of nodes Node temp= n1; n1= n2; n2= temp; } @SuppressWarnings("unchecked") /** Create an empty priority queue */ public PtrHeap(int initCapacity) { pq= (K[]) new Comparable[initCapacity+1]; size= 0; //this.comparator= comparator; //do we need to make it iterable; } /** Is the priority queue empty? */ public boolean isEmpty() { return (size==0); } //N will be size of our PQ;

/** Return the number of items on the priority queue. */ public int size() { return size; }

/** * Return the largest key on the priority queue. * Throw an exception if the priority queue is empty. */ public K max() //isRoot method { if(isEmpty()) throw new NoSuchElementException("Priority queue underflow"); else { return pq[1]; //remember in a maxOrientedHeap we will always keep index 1 as the largest value; } } public boolean less(K fst, K snd) { return fst.compareTo(snd) < 0; //true when i is smaller than j; }

public void sink(Node n) { } public void swim(Node n) { //first rule of swim is you do not talk about the swim function: that being said we need to // determine if our node is root within the while function and and it with while(n > 1 && less(n.parent,n)) //these are nodes you need to create your nodes up first; { exch(n, n.parent); //order of exchange does not matter since we are exchanging 2 items anyway; } } /** Add a new key to the priority queue. */ public void insert(K x) { //root = new Node(); n= new Node(); n.item= x; // this doesn't work; pq[++size]= x; swim (n); //while inserting we need to search for the exact location; we can do this by converting the size into its binary representation; //need to initialize n as new Node, put item in it and swim it; }

/** * Delete and return the largest key on the priority queue. * Throw an exception if the priority queue is empty. */ public K delMax() { if(isEmpty()) throw new NoSuchElementException("Priority queue underflow"); //first exchange max to the end of the list to erase exch(root,size); //exch(parent,lchild);normally we want to exchange index 1 with N; and then decrement N by one because we will be decreasing Node so size needs to go down by 1; return null; }

private void showHeap() { for(int i=1; i<= size;i++) StdOut.print(pq[i]+ " "); StdOut.println(); }

public static void main(String[] args) { PtrHeap pq = new PtrHeap<>(100); StdIn.fromString("10 20 30 40 50 - - - 05 25 35 - - - 70 80 05 - - - - "); while (!StdIn.isEmpty()) { StdOut.print ("pq: "); pq.showHeap(); String item = StdIn.readString(); if (item.equals("-")) StdOut.println("max: " + pq.delMax()); else pq.insert(item); } StdOut.println("(" + pq.size() + " left on pq)");

}

}