Binary heap: array representation, percolate, buildHeap, heapsort

A heap is the structure behind a priority queue: you reach the smallest (or largest) element in O(1) at any time, and insertion and deletion are O(log n). It is thought of as a tree but it is stored in an array, with no pointers. Almost always the same question comes in the exam: “Insert in this order / do this many deleteMin / apply buildHeap, write the final array.” Someone who does the two shifting operations on this page (percolate up and percolate down) correctly will not miss these questions.

Golden rules:

1. The structure rule: a heap is a complete binary tree. Levels are filled from left to right, with no gaps.
2. The order rule (min-heap): every node is less than or equal to its children. The smallest element is at the root.
3. Insertion goes up, deletion goes down. insert puts the element at the end and shifts it up. deleteMin puts the last element at the root and shifts it down.
4. Going down, swap with the smaller child. If you swap with the larger child, the order rule breaks.

Array representation

Because the tree is complete, it is enough to write the nodes into an array in level order. In this course (and in Weiss) the priority queue heap starts at index 1, and a[0] stays empty. Then the formulas are very clean:

index:  1   2   3   4   5   6   7   8
array: [6, 14,  9, 20, 17, 11, 30, 25]

              6
           /     \
         14       9
        /  \     /  \
      20    17  11   30
     /
   25

The index of 25 is 8, its parent is 8 / 2 = 4, that is, 20. Every parent is smaller than its children: this is a min-heap. But there is no order between siblings (such as 14 and 9). A heap is not a BST.

The height of a heap with n elements is $\lfloor \log_2 n \rfloor$. For 8 elements it is 3.

insert: percolate up

1. Put the new element in the first empty place (the end of the array, index size + 1).
2. While it is smaller than its parent, swap it with its parent.

Let’s insert 8 into the heap above:

8 at index 9: parent a[4]=20 > 8  → up
8 at index 4: parent a[2]=14 > 8 → up
8 at index 2: parent a[1]=6 < 8  → stop

[6, 8, 9, 14, 17, 11, 30, 25, 20]

              6
           /     \
          8       9
        /  \     /  \
      14    17  11   30
     /  \
   25    20

In the worst case the new element goes all the way up to the root: O(log n).

deleteMin: percolate down

1. Save the element at the root (the minimum); we will return it.
2. Move the last element to the root and reduce the size by 1.
3. Starting from the root: choose the smaller of the two children. If the child is smaller than the value you carry, swap and go down. If not, stop.

deleteMin on the 9-element heap from before:

6 is removed, the last element 20 goes to the root:
[20, 8, 9, 14, 17, 11, 30, 25]
i=1: children 8, 9   → 8 < 20, swap
i=2: children 14, 17 → 14 < 20, swap
i=4: child 25 (index 8) > 20 → stop

[8, 14, 9, 20, 17, 11, 30, 25]

PITFALL · The last element takes the place of the deleted one. There is no such thing as “moving the smaller child up to the root”. First the last element is put at the root, then it is shifted down. This way the tree stays complete and no gap appears.

buildHeap: O(n) construction

If you have n unordered elements there are two ways: n inserts (O(n log n)) or Floyd’s method. Floyd: put the elements into the array as they are, then call percolateDown at every node from the last internal node (n/2) toward the root. The leaves (those after n/2) are already heaps on their own, so they are not touched.

For [15, 12, 10, 8, 4, 6, 2, 9, 1, 3] (n = 10, i = 5, 4, 3, 2, 1):

    percDown(5) -> [15, 12, 10, 8, 3, 6, 2, 9, 1, 4]
    percDown(4) -> [15, 12, 10, 1, 3, 6, 2, 9, 8, 4]
    percDown(3) -> [15, 12, 2, 1, 3, 6, 10, 9, 8, 4]
    percDown(2) -> [15, 1, 2, 8, 3, 6, 10, 9, 12, 4]
    percDown(1) -> [1, 3, 2, 8, 4, 6, 10, 9, 12, 15]
  result: [1, 3, 2, 8, 4, 6, 10, 9, 12, 15]  moves=8

In the last step, 15 sinks from the root all the way to the bottom (index 10): 1, 3 and 4 each move up one level.

Why O(n)? percolateDown at a node does at most as much work as that node’s height. Half of the nodes are leaves (work 0), a quarter have height 1, an eighth have height 2, … The total:

$\sum_{h} \frac{n}{2^{h+1}} \cdot h \;\le\; n \sum_{h \ge 1} \frac{h}{2^{h+1}} = n$

So the work is small at the bottom where most nodes are, and large at the top where nodes are few. The average is constant, and the total is O(n). When building with insert, the opposite happens: most elements are at the bottom and each can climb all the way to the root.

MinHeap in Java

public class MinHeap {
    private int[] array = new int[11];   // array[0] is not used
    private int size = 0;

    public void insert(int x) {
        if (size + 1 == array.length)
            array = java.util.Arrays.copyOf(array, array.length * 2);
        int hole = ++size;
        while (hole > 1 && x < array[hole / 2]) {
            array[hole] = array[hole / 2];   // move the parent down
            hole /= 2;
        }
        array[hole] = x;
    }

    public int findMin() { return array[1]; }

    public int deleteMin() {
        if (size == 0) throw new RuntimeException("empty heap");
        int min = array[1];
        array[1] = array[size--];            // last element to the root
        percolateDown(1);
        return min;
    }

    private void percolateDown(int hole) {
        int tmp = array[hole];
        while (hole * 2 <= size) {
            int child = hole * 2;
            if (child != size && array[child + 1] < array[child]) child++;
            if (array[child] < tmp) array[hole] = array[child];
            else break;
            hole = child;
        }
        array[hole] = tmp;
    }

    public void buildHeap(int[] items) {
        array = new int[items.length + 1];
        size = items.length;
        for (int i = 0; i < items.length; i++) array[i + 1] = items[i];
        for (int i = size / 2; i > 0; i--) percolateDown(i);
    }

    public String toString() {           // array[1..size]
        return java.util.Arrays.toString(
            java.util.Arrays.copyOfRange(array, 1, size + 1));
    }
}

The code does not swap values at each step. It moves a “hole” and writes the element into place once at the end. A swap makes 3 assignments, moving the hole makes 1.

MinHeap h = new MinHeap();
for (int x : new int[]{6, 14, 9, 20, 17, 11, 30, 25}) h.insert(x);
h.insert(8);
System.out.println("+8 -> " + h);
System.out.println("deleteMin = " + h.deleteMin() + " -> " + h);

+8 -> [6, 8, 9, 14, 17, 11, 30, 25, 20]
deleteMin = 6 -> [8, 14, 9, 20, 17, 11, 30, 25]

Heapsort

Sorting with a heap: make the array a max-heap, then move the largest (the root) to the end and shrink the heap by one. No extra array is needed. In heapsort the array starts at index 0 (the array to be sorted is already like this), and the children are 2i + 1 and 2i + 2.

1. buildMaxHeap: from i = n/2 - 1 down to 0, percolateDown (for max) at each.
2. n - 1 times: swap a[0] with the last element of the heap, reduce the heap size by 1, and shift a[0] down.

For [4, 10, 3, 5, 1]:

== heapsort [4, 10, 3, 5, 1]
  after buildMaxHeap: [10, 5, 3, 4, 1]
  after deleteMax #1: [5, 4, 3, 1, 10]  (heap part size 4)
  after deleteMax #2: [4, 1, 3, 5, 10]  (heap part size 3)
  after deleteMax #3: [3, 1, 4, 5, 10]  (heap part size 2)
  after deleteMax #4: [1, 3, 4, 5, 10]  (heap part size 1)

At each step the sorted part on the right of the array grows by one. buildMaxHeap: for i=1 (10) the children 5, 1 are smaller, no change; for i=0 (4) the children are 10, 3, the larger 10 moves up, 4 is at index 1 with children 5, 1, the larger 5 moves up. Result [10, 5, 3, 4, 1].

Common mistakes

private void percolateDown(int hole) {
    int tmp = array[hole];
    while (hole * 2 <= size) {            // at least a left child exists
        int child = hole * 2;
        if (child != size && array[child + 1] < array[child])
            child++;                       // pick the smaller child
        if (array[child] < tmp)
            array[hole] = array[child];    // child moves up
        else
            break;
        hole = child;
    }
    array[hole] = tmp;
}