programmingconcepts

§ 2.6 · Data structures

Heaps

A tree where every parent is smaller than its children, kept in an array, so the minimum is always at the front.

A heap is a tree where every parent is smaller than its children (a min-heap), so the minimum is always at the root. It is stored in a plain array: the children of index i sit at 2i + 1 and 2i + 2. Inserting and removing the minimum take O(log n), which makes heaps the standard priority queue.

Push and pop
O(log n)
Peek at minimum
O(1)
Build from n items
O(n)
Children of i
2i + 1 and 2i + 2
Requires
ArraysBinary search trees
def push(heap, value):
    heap.append(value)
    i = len(heap) - 1
    while i > 0 and heap[(i - 1) // 2] > heap[i]:
        parent = (i - 1) // 2
        heap[i], heap[parent] = heap[parent], heap[i]
        i = parent


def pop(heap):
    top = heap[0]
    last = heap.pop()
    if not heap:
        return top
    heap[0] = last
    i = 0
    while True:
        smallest = i
        for child in (2 * i + 1, 2 * i + 2):
            if child < len(heap) and heap[child] < heap[smallest]:
                smallest = child
        if smallest == i:
            return top
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

step 1 / 1comparingswappingtaken

Fig. 2.6. The tree and the array below it are the same data. Orange marks values swapping as they sift; black marks the value just taken or settled.

Intuition

Think of an emergency room. Patients arrive in any order, but the most urgent is always seen next. Nobody sorts the whole waiting room; they only need to know who is first.

A heap gives exactly that: the smallest value (or largest, in a max-heap) on demand, with cheap inserts. It’s the usual way to build a priority queue.

How it works

The heap is a complete binary tree stored row by row in an array, so no pointers are needed. The node at index i has its children at 2i + 1 and 2i + 2, and its parent at (i − 1) ÷ 2.

  • Push: add the value at the end of the array, then sift up: while it’s smaller than its parent, swap them.
  • Pop: take the root. Move the last value to the root, then sift down: while it’s larger than its smaller child, swap with that child.

Both walk one path between the root and a leaf, and a complete tree has about log₂ n levels, so both are O(log n).

Where heaps are used

  • Priority queues, as in task schedulers and event simulations.
  • Dijkstra’s algorithm, which always expands the closest unvisited node.
  • Heapsort, which pops n times for an O(n log n), in-place sort.
  • Top-k problems: keep a heap of size k to find the k largest items in one pass.

Common mistakes

  1. Expecting sorted order. Iterating over a heap’s array does not give sorted output; only repeated pops do.
  2. Off-by-one parent formulas. With 0-based arrays, children are 2i + 1 and 2i + 2. The 1-based formulas (2i, 2i + 1) are different.
  3. Sifting down toward the wrong child. Always swap with the smaller child, or the heap property breaks on the other side.

In other languages

Language Heap in the standard library
Python heapq (a min-heap over a list)
JavaScript None
Java PriorityQueue (a min-heap by default)
C None
Go container/heap (you supply the ordering)
Rust BinaryHeap (a max-heap; wrap values in Reverse for a min-heap)

Check yourself

Check yourself

In a heap stored as an array, where are the children of index 2?

Check yourself

Push 1 into the min-heap [2, 5, 3]. Where does 1 end up?

Sources

  • J. W. J. Williams, “Algorithm 232: Heapsort,” Communications of the ACM 7, no. 6 (1964): 347–348.
  • Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 6, “Heapsort” (3rd edition).

Newsletter

One new concept each week, by email.

Signup opens soon.