Search tools and guides ⌘K
II · Trees, with shape

Heap (binary heap)

A priority queue you can grep.

1964 · J. W. J. Williams
The story

Williams introduced the heap in his 1964 heapsort paper — and accidentally invented the priority queue. The structure is a complete binary tree where each parent is ≤ its children (min-heap) or ≥ (max-heap), stored in an array using arithmetic indexing.

How it works

For node at index i: parent at (i−1)/2, children at 2i+1 and 2i+2. Insert appends and "sifts up"; extract-min replaces root with last leaf and "sifts down". Both are O(log n).

Where it lives

Dijkstra's algorithm. A* pathfinding. Job schedulers. Linux kernel's timerfd. heapq in Python's standard library. Top-k aggregations in Spark, Flink, ClickHouse.

The key insight

The "build heap in O(n)" result is one of the prettiest in algorithm analysis. Bottom-up heapify costs n × Σ(height/2^level) = O(n) — not O(n log n) as you'd expect.

More in Trees, with shape
Binary search tree Sorted, but with shortcuts. AVL tree Always height-balanced, to within one. Red-black tree Almost balanced, much faster to maintain. B-tree / B+ tree The shape of a database index. Skip list Probabilistic balance, beautifully. Trie (prefix tree) A tree you walk one character at a time. Segment tree Range queries in logarithmic time. Fenwick tree (BIT) Prefix sums, with constant tweaks. Treap BST and heap, secretly the same tree. Splay tree No metadata — and surprising amortised guarantees.
Across the cabinet
III Perfect hashing Zero collisions, by design. IV Bloom filter A set, in a thousandth of the space. IV HyperLogLog Count distinct, in 12 KB. IV Count-Min sketch Approximate frequencies, in tiny memory. IV MinHash Set similarity, in a few hashes. IV t-digest Quantiles, fairly accurate, fully streaming. V Suffix array All suffixes, sorted. V Suffix tree Every substring, in linear space.
← All data structures