Min Heap
What it is
A min-heap keeps the smallest value at the top. People also call this a priority queue. It does not keep every value in sorted order. Each parent is no larger than either of its children. Schedulers use heaps to find the next job due.
The core idea
A binary heap is a nearly full tree that fits in an array without needing any child links. The smallest value is at the root, so reading it takes O(1) time. The tree's height grows slowly with its size, so adding or removing a value can stay within O(log n) work: only a path through the tree needs attention. Pushing a value moves it up toward the root until it is in the right place. Popping moves the last value to the root and lets it sink down until it is in the right place. People call these two moves sift-up and sift-down. Unlike a sorted array, a heap does not make every value easy to find. It is useful when the next smallest value matters more than the full order.
Example
Push 5, 2, then 8. The top is 2. Pop returns 2 and leaves 5 at the top. The next pops return 5, then 8.
Where you meet this
- Go's runtime keeps "a heap of pointers to timers" for each processor, ordered by when each timer fires. It is a 4-ary heap, so each node has four children and the tree is shorter. (runtime/time.go)
- libevent keeps pending events in an array-based min heap ordered by timeout. (minheap-internal.h)
- Python's
heapqand Go'scontainer/heapgive you a heap to build a priority queue. Theheapqdocs call a heap "a good structure for implementing schedulers". (heapq, container/heap)
When to choose it: you keep adding items and keep taking out the smallest one, like the next timer, the next job, or the closest unvisited point in a route search.
When not to: you need every item in sorted order at once (just sort), or you need to find or change an item in the middle (a heap cannot find it without help). With huge numbers of timers that do not need exact times, systems sometimes use a "timer wheel" instead. The heapq docs note that other structures can be faster on average, but their worst case can be terrible, while a heap's worst case stays close to its average.
Common bugs
- Returning values in arrival order.
- Leaving a parent larger than a child after a change.
- Handling one branch correctly but not the other.
- Dropping duplicate values.
- Letting peek change the size.
- Comparing by subtraction when that subtraction can overflow.
Keep it fast
Push and pop should walk only the tree's height. Do not scan all values to find the minimum.
Learn more
Algorithms textbooks explain heapsort, Dijkstra's algorithm, and Prim's algorithm. All use the same idea of choosing the smallest item quickly.