1. Binary Heaps and Heapsort
Binary heaps were invented as part of heapsort but it turned out that the binary heap data structure was more important than the sorting algorithm. Binary heaps are generally the preferred data structure for implementing priority queues.
The two key operations for manipulating binary heaps are what I'll call siftUp and siftDown. (The textbook buries these operations inside of other methods). When you have a heap structure except that a single item may violate the heap ordering because it's priority is too large or too small, then we can fix it by calling siftUp or siftDown respectively. Once we have these two methods, anything we could want to do on binary heaps becomes trivial. The index computations for the parent and children of a node work out more nicely if we do not use array element [0]. The shown code makes this assumption.
int extractMax()
{
int val = a[1];
a[1] = a[N--];
siftDown( 1 );
return val;
}
void insert( int v )
{
a[++N] = v;
siftUp( N );
}
void increasePri( int ndx, int pri )
{
a[ndx] = pri;
siftUp( ndx );
}
void decreasePri( int ndx, int pri )
{
a[ndx] = pri;
siftDown( ndx );
}
void heapsort(itemType a[], int N)
{
int k;
for (k = N/2; k >= 1; k--)
siftDown( k );
for (i = N; i >= 1; i--)
a[i] = extractMax();
}
So the key missing pieces are sift up and sift down. The following are good solutions (parent(pos) returns the index of the parent of the node at index pos, and similarly for leftChild(pos))
private void siftUp( int pos )
{
a[0] = a[pos]; // use a[0] as a temp!
while (a[ parent(pos) ] < a[0])
{
a[pos] = a[ parent(pos) ];
pos = parent(pos);
}
a[pos] = a[0];
}
private void siftDown( int pos )
{
int v = a[pos];
while (leftChild(pos) <= N)
{
int maxChild = leftChild(pos);
if (maxChild < N && a[maxChild] < a[ maxChild+1 ]) maxChild++;
if (a[pos] > a[maxChild]) break;
a[pos] = a[maxChild];
pos = maxChild;
}
a[pos] = v;
}
The index computations can be computed simply as follows
public static int parent( int n ) { return n/2; }
public static int leftChild( int n ) { return 2*n; }
public static int rightChild( int n ) { return 2*n + 1; }
Sometimes the index computations are written in a more efficient manner that takes advantage of the binary representation of integers. In base 10, multiplying and divide by 10 has the effect of shifting the digits (or equivalently the decimal point). Similarly in base 2, multiplying and dividing by 2 simply shifts the bits. Java has the bit-shifting operators << and >> so we can use these instead of multiplication and division. When computing the right child index, we add 1 to an even number. In binary this can be accomplish by flipping the rightmost bit from a 0 to a 1. We can accomplish this by doing a bit-wise OR with the value 1. With these modifications, we get the following faster versions.
public static int parent( int n ) { return n>>1; }
public static int leftChild( int n ) { return n<<1; }
public static int rightChild( int n ) { return (n<<1) | 1; }