Trees & Structures

Binary Heap

A tree packed into an array that always serves the smallest item next — the engine inside a priority queue.

The heap as a tree (and its backing array below). The green root is the current minimum; blue is the element sifting; orange is the one it's compared/swapped against. The green row is the sorted output.

What you're seeing

A binary heap is a tree with a strict rule — every parent is no larger than its children — but it's stored as a plain array, with node i's children at 2i+1 and 2i+2. To insert, drop the value in as a new leaf and let it "sift up," swapping with its parent until it's no longer smaller. To extract the minimum, take the root, move the last leaf up to fill the hole, and let it "sift down," swapping with its smaller child until order is restored. Here we insert a batch of values, then extract-min repeatedly — and the values come out in sorted order.

The rule

insert(x):     append x as a leaf
               while x < parent(x): swap up        # sift up

extract_min(): m = root
               move last leaf to the root
               while root > smaller child: swap down # sift down
               return m

children of i: 2i+1, 2i+2     parent of i: (i-1)/2

The invariant

The one rule, maintained at all times, is the heap property: every node is ≤ both of its children. From it, the minimum of the whole heap must sit at the root (anything smaller would violate the property somewhere on the path up). Each operation breaks the property in exactly one place and walks it back: sift-up fixes a child that's smaller than its parent by trading them, moving the violation one level up until it's gone; sift-down does the mirror, pushing a too-large parent down past its smaller child. Because the tree is kept complete (filled level by level — which is what lets it live in a gap-free array), its height is ⌊log₂ n⌋, so each sift touches at most that many levels. The "always-min-at-root" guarantee is what makes the heap a priority queue.

The cost

insertextract-minpeek-min TimeO(log n)O(log n)O(1)

A sift walks one root-to-leaf path, so it's O(log n); reading the minimum is free. The array layout means no pointers and excellent cache behavior. Building a heap from n items by repeated insertion is O(n log n), but a bottom-up "heapify" does it in O(n). Draining the heap with n extract-mins yields the values in sorted order in O(n log n) — which is exactly heapsort, an in-place, worst-case-guaranteed sort.

In the wild

The binary heap is the default priority queue, and priority queues are everywhere: Dijkstra's and A*'s frontier, event-driven simulation, OS process scheduling, Huffman-code construction, k-way merging and external sorting, and "top-k" / streaming-median problems. It backs heapq in Python, std::priority_queue in C++, and PriorityQueue in Java. Variants trade the constant factors — d-ary heaps (more children, shallower), pairing and Fibonacci heaps (faster decrease-key for graph algorithms) — but the binary heap's simplicity and cache-friendliness make it the everyday choice.

Try this

Watch the extract phase: each time the root (green) leaves, the last leaf jumps to the top and tumbles back down to its level. Notice the output row is always sorted — the heap is sorting for you, one cheap O(log n) extraction at a time.

References

  1. Williams, J. W. J. "Algorithm 232: Heapsort." Communications of the ACM 7(6):347–348, 1964. The binary heap + heapsort.
  2. Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §6 (Heapsort) and §6.5 (Priority queues). MIT Press, 2022.
  3. Sedgewick & Wayne. Algorithms, 4th ed., §2.4 (Priority Queues). algs4.cs.princeton.edu/24pq.