Binary heaps

A heap gives access to the smallest element (min-heap) or the largest (max-heap) in O(1), and lets you remove it or insert a new element in O(log n). It is the structure behind priority queues, heapsort and Dijkstra's algorithm.

Two rules

1. Shape: the tree is almost complete. Every level is full except possibly the last, which fills from left to right.
2. Order: a node's key is always better than its children's (smaller in a min-heap, larger in a max-heap).

Unlike a BST, there is no order between siblings: a heap is not sorted, it only guarantees that the root is the minimum (or maximum).

Array storage

Because the tree is almost complete, it is stored level by level in an array, with no pointers. For the element at index i (starting at 0):

• parent: ⌊(i − 1) / 2⌋
• left child: 2i + 1
• right child: 2i + 2

The min-heap [3, 8, 5, 12, 10, 7] is this tree:

          3
        /   \
       8     5
      / \   /
    12  10 7

Insert: place, then sift up

1. Put the new element in the next free slot (the end of the array) to keep the shape.
2. While it is better than its parent, swap them (sift up).

Example: insert 4 into [3, 8, 5, 12, 10, 7]. 4 goes to index 6, whose parent is index 2 (5). 4 < 5: swap. The new parent is 3, and 4 ≥ 3: stop. Result: [3, 8, 4, 12, 10, 7, 5].

ExtractMin: replace, then sift down

1. Remove the root and replace it with the last element of the array. Removing the root directly would leave a hole.
2. While a child is better than it, swap it with the better of the two children (sift down).

Example: ExtractMin on [3, 8, 5, 12, 10, 7]. Remove 3 and put 7 at the root: [7, 8, 5, 12, 10]. The children of 7 are 8 and 5; the smaller is 5, and 5 < 7: swap. 7 has no children left. Result: [5, 8, 7, 12, 10].

Building a heap in O(n)

Starting from an arbitrary array, you could insert the elements one at a time, which costs O(n log n). There is a better way: sift down every internal node, from the last parent (index ⌊n/2⌋ − 1) up to the root.

Example: [9, 4, 7, 1, 8, 2], n = 6, start at index 2.

1. Index 2 (7): its child 2 is smaller → swap. [9, 4, 2, 1, 8, 7]
2. Index 1 (4): its children are 1 and 8; 1 < 4 → swap. [9, 1, 2, 4, 8, 7]
3. Index 0 (9): its children are 1 and 2; 1 < 9 → swap. Then 9 has children 4 and 8; 4 < 9 → swap. [1, 4, 2, 9, 8, 7]

Why O(n)? Half of the nodes are leaves and never move. A quarter can sift down at most 1 level, an eighth at most 2, and so on. The sum n/4 · 1 + n/8 · 2 + n/16 · 3 + … is bounded by n.

Complexity

Heapsort uses a max-heap: build the heap in O(n), then extract the maximum n times, for a total of O(n log n) with no extra memory.