2431 Fast insert Develop a comparebased implementation of th

2.4.31 Fast insert. Develop a compare-based implementation of the MinPQ API such
that insert uses ~ log log N compares and delete the minimum uses ~2 log N compares.
Hint : Use binary search on parent pointers to find the ancestor in swim().(Please give java based implementation)

Solution

//Priority Queue
public class MaxPQ<Key extends Comparable<Key>>
{
private Key[] pq;
private int N;
public MaxPQ(int capacity){
pq = (Key[]) new Comparable[capacity+1];

}

/// PQ ops
public boolean isEmpty()
{ return N == 0; }
public void insert(Key x) // 06:27
{
pq[++N] = x;
swim(N);
}
public Key delMax() // 10:03
{
Key max = pq[1];
// Exchange root(max) with node at end,
exch(1, N--);
// then sink new root down to where it belongs.
sink(1);
//Prevent loitering by nulling out max position
pq[N+1] = null;
return max;
}

/// helper functions
private void swim(int k) // 05:15
{
while(k>1 && less(k/2, k))
{
exch(k, k/2);
k = k/2;
}
}
private void sink(int k) // 8:52
{
while (2*k <= N)
{
int j = 2*k;
// Check if we are going off the end of the and which child is larger
if (j < N && less(j, j+1)) j++;
//If k is not less than either child, then we are done
if (!less(k,j)) break;
//If k is larger than a child, exchange
exch(k,j);
k = j;
}
}

// array help functions
private boolean less(int i, int j)
{
return pq[i].compareTo(pq[j]) < 0; }
private void exch(int i, int j)
{ Key t = pq[i]; pq[i] = pq[j]; pq[j] = t; }
}