Binary heap visualization

A binary min-heap is a collection that always gives you its smallest value first. It is a complete binary tree stored in an ordinary array, with one rule: no value is smaller than its parent. So the minimum is always at the root, heap[0], and you can read it in one step.

How it works

The tree has no pointers. In the array, the children of index i are 2i + 1 and 2i + 2, and its parent is floor((i - 1) / 2). The book (CLRS) counts from 1; this code counts from 0. The tree is filled from the top, left to right, so it never has gaps.

1. Insert: put the value in the first free slot, the end of the array. While it is smaller than its parent, swap them. This is sift-up.
2. Extract the minimum: keep heap[0]. Move the last value to the root and shorten the array. While that value is larger than one of its children, swap it with the smaller child. This is sift-down.

Time and space complexity

The tree has about log n levels, and a sift walks at most one path.

• Read the minimum: O(1), it is the root.
• Insert: O(log n) in the worst case, when the new value is the new minimum. A value that is not smaller than its parent does no swap, which is why the best case is O(1).
• Extract the minimum: O(log n). The value that replaces the root came from the bottom, so it usually sinks back down.
• Space: O(n), the array.

A worked example

Insert 9, 4, 7, 1, 6, 2 and 5 into an empty min-heap, then take the minimum out until it is empty. First the inserts. The array is shown after each one, with the swaps that sift-up made.

Now extractMin. The first call returns 1, the root. The last value, 5, moves to the root and the array becomes 5, 4, 2, 9, 6, 7. Sift-down compares 5 with its children 4 and 2, swaps with the smaller one, 2, and gives 2, 4, 5, 9, 6, 7. The new child of 5 is 7, which is not smaller, so it stops. The table gives the array after each call.

The values come out as 1, 2, 4, 5, 6, 7, 9: sorted, because the smallest remaining value is always at the root. The array itself is not sorted, for example 1, 4, 2, 9, 6, 7, 5 after the inserts. It is only ordered along each path from a leaf to the root. The whole run records 20 comparisons.

Pseudocode

This is the lesson's min-heap with indexes from 0, so PARENT(i) is floor((i - 1) / 2). CLRS counts from 1 and builds a max-heap; the code for a min-heap only reverses the comparisons. H.length is the number of values in the heap.

MIN-HEAP-INSERT(H, v)
    H[H.length] = v
    i = H.length - 1
    while i > 0 and H[PARENT(i)] > H[i]
        swap H[i] and H[PARENT(i)]
        i = PARENT(i)

EXTRACT-MIN(H)
    if H.length == 0
        return NIL            // underflow
    min = H[0]
    H[0] = H[H.length - 1]
    H.length = H.length - 1
    SIFT-DOWN(H, 0)
    return min

SIFT-DOWN(H, i)
    while true
        l = 2i + 1
        r = 2i + 2
        smallest = i
        if l < H.length and H[l] < H[smallest]
            smallest = l
        if r < H.length and H[r] < H[smallest]
            smallest = r
        if smallest == i
            return
        swap H[i] and H[smallest]
        i = smallest

Each round of either loop moves one level, and the tree has about log n levels. In SIFT-DOWN the value is compared with both children, and it swaps with the smaller one.

When to use it, and when not to

Use a heap when you repeatedly need the smallest item of a changing set: a priority queue. Dijkstra's algorithm takes the closest unfinished node each round, and a heap makes that step O(log n) instead of a scan of every node.

A heap is not sorted. Only the minimum is easy to find; any other value takes O(n) to look up.

Where it is used

• Priority queues in standard libraries. Java's PriorityQueue is documented as based on a priority heap, with O(log n) offer and poll and constant-time peek. Python's heapq module keeps a binary min-heap in an ordinary list with zero-based indexes, the same layout as this lesson.
• Timers and event simulation. A scheduler that must run the task due soonest, or a simulation that must process the earliest event next, keeps its pending items in a min-heap keyed by time. Adding an item and taking the next one each cost O(log n), and no sorted list is kept up to date.
• Top k and merging. To find the k largest values in a long stream, keep a min-heap of k values. A new value larger than the root replaces it, at O(log k). To merge k sorted lists, keep the front value of each list in a heap, take the minimum and add the next value from the same list: O(n log k) for n values in total.

Variations and related ideas

A max-heap reverses every comparison and keeps the largest value at the root; heap sort uses one to sort an array in place. A d-ary heap gives each node d children, which makes the tree shorter and sift-up cheaper at the cost of a wider sift-down. A heap implements the priority queue that a plain queue cannot be: the queue orders by arrival, the heap by value. Dijkstra's algorithm is the standard user. If you also need the keys in sorted order or range lookups, a binary search tree keeps that order, at the price of a more complex structure.