//Trying to impelement a MaxBinaryHeap using linkedlists. I need to find the lastNode using binary representation which where my problems start, I am not sure about my FindLastNode, swim and delmax() functions. Looking forward to your insights.

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.

*/

public class PtrHeap> {

public static class Node {

K value;

Node parent;

Node lchild;

Node rchild;

}

private int size;

private Node root;

private K[] pq;

public void Node(K value, Node parent)

{

root= null;

root.parent=null;

}

boolean isRoot(Node n){ return n == root; }

Node find(int n){ return null; }

void exch(Node n1, Node n2)

{

K temp= n1.value;

n1.value= n2.value;

n2.value= temp;

}

@SuppressWarnings("unchecked")

public PtrHeap(int initCapacity)

{

pq= (K[]) new Comparable[initCapacity+1];

size= 0;

root= null;

}

public boolean isEmpty()

{ return (size==0); }

public int size() { return size; } //size gives us the location of our lastNode ?? Continue from here 03/10/2021 Hour 03:44 AM

public K max()

{

if(size==0) throw new NoSuchElementException("Priority queue underflow");

else

{

return pq[1];

}

}

public boolean less(K fst, K snd)

{

return fst.compareTo(snd) < 0;

}

public void sink(Node n)

{

if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");

Node sinkNode = n;

while(sinkNode.lchild!= null || sinkNode.rchild != null)

{

if( sinkNode.rchild != null && less(sinkNode.lchild.value,sinkNode.rchild.value))

{

sinkNode.lchild= sinkNode.rchild;

}

if(less(sinkNode.lchild.value,sinkNode.value)) { break; }

exch(sinkNode, sinkNode.lchild);

sinkNode= sinkNode.lchild;

}

}

public void swim(Node n)

{ if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");

while(n.parent!= null && less(n.parent.value, n.value))

{

exch(n, n.parent);

n= n.parent;

}

}

public Node lastChild()

{

Node ourLast= root;

String lastNode= Integer.toBinaryString(size()+1);

char [] lastNodePos= lastNode.toCharArray();

for(int i=1; i < lastNodePos.length; i++)

{

if(lastNodePos[i] == 0) { ourLast= ourLast.lchild; }

if(lastNodePos[i] == 1) { ourLast= ourLast.rchild; }

}

System.out.println(ourLast.value);

return ourLast;

}

public void insert(K x)

{

Node node= new Node();

node.value= x;

node.lchild= null;

node.rchild= null;

String s= Integer.toBinaryString(size()+1);

char [] pos = s.toCharArray();

if (size==0) { root=node; }

else

{ Node ourLast= null;

for(int i=1; i < pos.length-1; i++)

{

if(pos[i] == 0) { ourLast= ourLast.lchild; }

if(pos[i] == 1) { ourLast= ourLast.rchild; }

}

if(pos.length-1==0)

{

ourLast.lchild= node;

}

else

{

ourLast.rchild= node;

}

}

swim(node);

}

public K delMax() {

if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");

K maxValue= root.value;

Node lastChild= lastChild();

exch(root, lastChild);

sink(root);

Node max= null;

while(lastChild.lchild!= null )

{

max= lastChild.rchild;

}

return max.value;

}

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<>(10);

StdIn.fromString("10 20 40 - - 10 - 20 - 20 40 40 - ");

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)");

}

}