We learned in the last post about possible ways of implementing a priority queue data type. In this part, we’re going to talk about representing a heap internally. We create a private array pq[] of length N+1. Our array will be 1-indexed.
Implementation and algorithms
Heapifying
As we have seen in the previous parts, for a max-oriented heap to be valid, a condition must hold. That is, the root node, which is the element at index k, is bigger than or equal to both its children, at 2k and 2k+1.
There are cases when this property is temporarily violated and should be corrected:
- When a new node is inserted at the end (of the pq[] array) or if a value of the key becomes larger than its parent. (Parent must be larger)
- When the root (max, in case of a max-heap) is removed.
- When a node’s value becomes smaller than one of its children (the node is no more the max of the sub-heap)
Bottom-up reheapifying (swim)
If a violation happens and a node’s key becomes larger than its parent, we can fix this by exchanging the node with its parent.
If the node is still larger, which is the same case as the image above, we can fix it the exact same way we did: we exchange it again with its parent.
We keep going up the heap until we find that the key is not larger than the one in the parent or if we reached the root then we stop the swimming.
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k/2, k);
k = k/2;
}
}
Top-down reheapifying (sink)
This is the second violation that we might have: a node is smaller than one or both of its children. We can do a slightly different approach than the previous violation fix, but similar in concept: we will exchange that node with the larger of its children. If there’s still a violation at the child, we can keep doing the same thing: pushing the node down the heap by exchanging with the larger of children, until we either reach a case where both children are smaller so the node would be indeed the max or we hit the bottom of the heap (end of the pq[]).
Let’s take a look at the implementation:
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;
}
}
Complete implementation of a Heap priority queue
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq; // heap-ordered complete binary tree
private int N = 0; // in pq[1..N] with pq[0] unused
public MaxPQ(int maxN) {
pq = (Key[]) new Comparable[maxN+1];
}
public boolean isEmpty() { return N == 0; }
public int size() { return N; }
public void insert(Key v) {
pq[++N] = v;
swim(N);
}
public Key delMax() {
Key max = pq[1]; // Retrieve max key from top.
exch(1, N--); // Exchange with last item.
pq[N+1] = null; // Avoid loitering.
sink(1); // Restore heap property.
return max;
}
private boolean less(int i, int j)
private void exch(int i, int j)
private void swim(int k)
private void sink(int k)
}
Code is courtesy of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. Chapter 2, page 318.
