Heaps & Priority Queues
A heap is a complete binary tree that satisfies the heap property: every parent is smaller (min-heap) or larger (max-heap) than its children. A priority queue is the abstract data type; a heap is the most common implementation. Together, they solve a class of problems — Top-K, scheduling, median maintenance, merge K sorted streams — with elegant efficiency.
This is lesson 7 of Module 3 — Trees in DSA: Zero to Mastery. It assumes the tree vocabulary and height bounds from Trees. Previous lesson: Treaps, Splay Trees & Skip Lists. Next: Tries in Depth. Module index: /algorithms/trees/.
Why heaps exist
Many programs repeatedly ask one question: of everything waiting, which item matters most right now? An operating system asks it about timers ("which one expires next?"), a network simulator about events, Dijkstra's algorithm about the closest unsettled vertex, a merge step about the smallest head among sorted runs, a job runner about the highest-priority task. The priority queue abstract data type captures exactly that: insert(item, priority), peek() the best item, pop() the best item. Nothing else is promised — in particular, no ordered iteration and no fast search.
The obvious implementations each fail one side. An unsorted array inserts in but finds the minimum in . A sorted array finds it in but inserts in . A balanced BST does both in but pays for a total order it does not need, with pointer-heavy nodes. The binary heap keeps only a partial order — each parent beats its children — which is just enough to keep the best item at the root and cheap enough to restore in after any change. It needs no pointers at all: a complete binary tree fits in a plain array.
J. W. J. Williams introduced the binary heap in 1964 as the data structure behind heapsort, and Robert Floyd published the bottom-up construction the same year. D. B. Johnson generalised it to d-ary heaps in 1975 to speed up Dijkstra's algorithm. Vuillemin's binomial queues (1978) added fast merging, and Fredman and Tarjan's Fibonacci heaps (1987) made decrease-key amortized, improving the theoretical bound for Dijkstra and Prim. Today the humble binary (or 4-ary) array heap is what nearly every standard library ships: Python's heapq, Java's PriorityQueue, C++'s std::priority_queue, Go's container/heap.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "k-th largest", "k-th smallest", "top k", "k closest" | Heap of size (min-heap for largest, max-heap for smallest), or quickselect if offline |
| "repeatedly take the smallest/largest and put something back" | Heap simulation (Last Stone Weight, Huffman coding, connecting ropes) |
| "merge k sorted lists/arrays/streams", "k-th smallest in a sorted matrix" | k-way merge: heap of the current heads, size |
| "median of a stream", "balance two halves", "sliding window median" | Two heaps (max-heap low half, min-heap high half), lazy deletion for windows |
| "minimum number of rooms/servers/platforms", "schedule meetings" | Sort by start, min-heap of end times — see Intervals |
| "shortest path with non-negative weights", "minimum spanning tree (Prim)" | Priority queue keyed by tentative distance, lazy deletion of stale entries |
| "process tasks by priority/deadline", "CPU with cooldown", "IPO / maximise capital" | Max-heap of available items, often plus a sorted list of not-yet-available items |
| "smallest range covering one element from each list" | k-way merge heap plus tracking the current maximum |
| "events in time order", "simulate", "next timer to fire" | Min-heap keyed by time (or a timing wheel at scale) |
| "stream too big to sort", "only need the best few" | Bounded heap: time, memory |
A negative trigger: if you also need "find/delete an arbitrary element", "iterate in order" or "rank of x", a heap is the wrong tool; use a balanced BST or a sorted container (see the comparison table below).
Heap Fundamentals
Structure
A heap is a complete binary tree stored as an array. For a node at index (0-indexed):
- Left child:
- Right child:
- Parent:
graph TD
A["1<br/><small>idx 0</small>"] --> B["3<br/><small>idx 1</small>"]
A --> C["2<br/><small>idx 2</small>"]
B --> D["7<br/><small>idx 3</small>"]
B --> E["6<br/><small>idx 4</small>"]
C --> F["5<br/><small>idx 5</small>"]
C --> G["4<br/><small>idx 6</small>"]
style A fill:#4CAF50,color:#fff
Array representation: [1, 3, 2, 7, 6, 5, 4]
Why the index formulas work
Claim. If a complete binary tree is stored level by level, left to right, starting at index 0, then the children of index are at and , and the parent of is at .
Proof. Level holds nodes (every level except possibly the last is full), and the levels before it hold nodes, so level occupies indices through . Take node on level at position within its level. The nodes to its left on level each have two children on level , and those come first, so 's left child is at position on level , which is index
and the right child is the next slot, . Inverting: a child is either (odd ) or (even ); in both cases . ∎
Three consequences you will use constantly:
- Leaves are the second half. Node has a child iff , i.e. . So indices — about half the array — are leaves. Bottom-up heapify starts at for this reason.
- Height is . A complete tree is as short as a binary tree with nodes can be (the height bound in Trees), so every root-to-leaf path has at most edges. A heap of a million items is 19 levels deep.
- 1-indexed variant. With the root at index 1 (Sedgewick, the old
IndexedMinPQbelow), children are and and the parent is — one less addition per step, at the cost of a wasted slot. For a d-ary heap (0-indexed), children of are and the parent is ; the same proof works with in place of 2.
Shape is guaranteed by construction: we only ever add at index and remove from index , so the tree stays complete and never needs rebalancing. Order is the only thing the operations have to repair.
Min-Heap vs Max-Heap
| Property | Min-Heap | Max-Heap |
|---|---|---|
| Root | Smallest element | Largest element |
| Parent vs children | Parent children | Parent children |
| Extract operation | Returns minimum | Returns maximum |
| Use case | Priority queues, Dijkstra | Max priority, heap sort |
Operations Complexity
| Operation | Time |
|---|---|
| Insert (push) | |
| Extract min/max (pop) | |
| Peek (get min/max) | |
| Build heap from array | |
| Search for arbitrary element | |
| Delete arbitrary element | (find) + (remove) |
Sift-up and sift-down: the two repairs
Every heap operation is "change the array in one place, then repair the heap property along one path". There are exactly two repairs.
- Sift-up (also called swim, bubble-up, percolate-up). Used after push: the new item sits at the last index and may be smaller than its parent. Compare with the parent; if the parent is larger, swap and continue from the parent's index; stop when the parent is not larger or the root is reached. At most swaps, one comparison each.
- Sift-down (sink, bubble-down, heapify). Used after pop: the root is removed, the last item is moved into index 0, and it may be larger than its children. Find the smaller child; if it is smaller than the item, swap and continue from the child's index; stop at a leaf or when both children are at least as large. At most swaps, two comparisons each.
flowchart TD
PUSH["push x: append at index n"] --> UP{"parent larger than x?"}
UP -->|"yes"| SWU["swap with parent, i = parent"]
SWU --> UP
UP -->|"no, or i = 0"| DONE1["heap restored"]
POP["pop: save a[0], move last item to index 0"] --> DOWN{"smaller child less than a[i]?"}
DOWN -->|"yes"| SWD["swap with smaller child, i = child"]
SWD --> DOWN
DOWN -->|"no, or i is a leaf"| DONE2["return saved root"]
Why pick the smaller child in a min-heap sift-down: after the swap, that child becomes the parent of the other child. Only the smaller of the two is guaranteed to be ≤ its new sibling-turned-child. Swapping with the larger child would create a new violation one level up.
Trace: push 5, 3, 8, 1, 9, 2, then pop twice
Computed by running the binary min-heap and logging every comparison that changes or ends a sift (the same run as the visualizer below). Index arithmetic: parent of is .
| Step | Operation | What happens | Array after |
|---|---|---|---|
| 1 | push 5 | append at index 0 | [5] |
| 2 | index 0 is the root, stop | [5] | |
| 3 | push 3 | append at index 1 | [5, 3] |
| 4 | parent 5 at index 0 is larger: swap indices 1 and 0 | [3, 5] | |
| 5 | reached the root, stop | [3, 5] | |
| 6 | push 8 | append at index 2 | [3, 5, 8] |
| 7 | parent 3 at index 0: 3 <= 8, stop | [3, 5, 8] | |
| 8 | push 1 | append at index 3 | [3, 5, 8, 1] |
| 9 | parent 5 at index 1 is larger: swap indices 3 and 1 | [3, 1, 8, 5] | |
| 10 | parent 3 at index 0 is larger: swap indices 1 and 0 | [1, 3, 8, 5] | |
| 11 | reached the root, stop | [1, 3, 8, 5] | |
| 12 | push 9 | append at index 4 | [1, 3, 8, 5, 9] |
| 13 | parent 3 at index 1: 3 <= 9, stop | [1, 3, 8, 5, 9] | |
| 14 | push 2 | append at index 5 | [1, 3, 8, 5, 9, 2] |
| 15 | parent 8 at index 2 is larger: swap indices 5 and 2 | [1, 3, 2, 5, 9, 8] | |
| 16 | parent 1 at index 0: 1 <= 2, stop | [1, 3, 2, 5, 9, 8] | |
| 17 | pop → 1 | remove root 1, move last item 8 to index 0 | [8, 3, 2, 5, 9] |
| 18 | children 3 (idx 1) and 2 (idx 2); smaller is 2 < 8: swap 0 and 2 | [2, 3, 8, 5, 9] | |
| 19 | 8 at index 2 is a leaf (index 5 is past the end), stop | [2, 3, 8, 5, 9] | |
| 20 | pop → 2 | remove root 2, move last item 9 to index 0 | [9, 3, 8, 5] |
| 21 | children 3 (idx 1) and 8 (idx 2); smaller is 3 < 9: swap 0 and 1 | [3, 9, 8, 5] | |
| 22 | only child 5 (idx 3) < 9: swap 1 and 3 | [3, 5, 8, 9] | |
| 23 | 9 at index 3 is a leaf, stop | [3, 5, 8, 9] |
The final array [3, 5, 8, 9] matches what Python's heapq produces for the same operations. Notice that after step 16 the array [1, 3, 2, 5, 9, 8] is not sorted: a heap is only partially ordered, which is the whole point — it is cheaper to maintain.
Min-Heap Implementation
The canonical binary heap in four languages. Python and TypeScript are the original integer min-heap; the Java and C++ versions are generic over the element type with a comparator, which is how you would ship one. All four run the same test: the trace above, then 1,000 pseudo-random values (MINSTD generator, seed 42, values mod 1000 so there are duplicates) pushed and popped, checked against a sort.
class MinHeap:
def __init__(self):
self.heap: list[int] = []
def __len__(self) -> int:
return len(self.heap)
def peek(self) -> int:
return self.heap[0]
def push(self, val: int) -> None:
self.heap.append(val)
self._bubble_up(len(self.heap) - 1)
def pop(self) -> int:
if len(self.heap) == 1:
return self.heap.pop()
min_val = self.heap[0]
self.heap[0] = self.heap.pop()
self._bubble_down(0)
return min_val
def _bubble_up(self, idx: int) -> None:
while idx > 0:
parent = (idx - 1) // 2
if self.heap[parent] <= self.heap[idx]:
break
self.heap[parent], self.heap[idx] = self.heap[idx], self.heap[parent]
idx = parent
def _bubble_down(self, idx: int) -> None:
n = len(self.heap)
while True:
smallest = idx
left = 2 * idx + 1
right = 2 * idx + 2
if left < n and self.heap[left] < self.heap[smallest]:
smallest = left
if right < n and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest == idx:
break
self.heap[idx], self.heap[smallest] = self.heap[smallest], self.heap[idx]
idx = smallest
# --- shared test (identical in all four languages) ---
h = MinHeap()
for x in [5, 3, 8, 1, 9, 2]:
h.push(x)
assert h.heap == [1, 3, 2, 5, 9, 8] and h.peek() == 1
assert h.pop() == 1 and h.pop() == 2
assert h.heap == [3, 5, 8, 9]
assert [h.pop() for _ in range(4)] == [3, 5, 8, 9] and len(h) == 0
x, vals = 42, []
for _ in range(1000):
x = x * 48271 % 2147483647
vals.append(x % 1000)
for v in vals:
h.push(v)
assert [h.pop() for _ in range(1000)] == sorted(vals)
print("ok")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.NoSuchElementException;
public class BinaryHeapDemo {
/** Array-backed binary heap; the comparator decides min-heap or max-heap. */
static final class BinaryHeap<T> {
private final List<T> a = new ArrayList<>();
private final Comparator<? super T> cmp;
BinaryHeap(Comparator<? super T> cmp) { this.cmp = cmp; }
int size() { return a.size(); }
T peek() {
if (a.isEmpty()) throw new NoSuchElementException();
return a.get(0);
}
void push(T x) {
a.add(x);
int i = a.size() - 1;
while (i > 0) { // sift-up
int p = (i - 1) / 2;
if (cmp.compare(a.get(p), a.get(i)) <= 0) break;
swap(i, p);
i = p;
}
}
T pop() {
if (a.isEmpty()) throw new NoSuchElementException();
T top = a.get(0);
T last = a.remove(a.size() - 1);
if (!a.isEmpty()) {
a.set(0, last);
int i = 0, n = a.size();
while (true) { // sift-down
int l = 2 * i + 1, r = l + 1, s = i;
if (l < n && cmp.compare(a.get(l), a.get(s)) < 0) s = l;
if (r < n && cmp.compare(a.get(r), a.get(s)) < 0) s = r;
if (s == i) break;
swap(i, s);
i = s;
}
}
return top;
}
List<T> snapshot() { return new ArrayList<>(a); }
private void swap(int i, int j) { T t = a.get(i); a.set(i, a.get(j)); a.set(j, t); }
}
static void check(boolean cond) { if (!cond) throw new AssertionError(); }
public static void main(String[] args) {
BinaryHeap<Integer> h = new BinaryHeap<>(Comparator.naturalOrder());
for (int x : new int[] {5, 3, 8, 1, 9, 2}) h.push(x);
check(h.snapshot().equals(List.of(1, 3, 2, 5, 9, 8)) && h.peek() == 1);
check(h.pop() == 1 && h.pop() == 2);
check(h.snapshot().equals(List.of(3, 5, 8, 9)));
for (int want : new int[] {3, 5, 8, 9}) check(h.pop() == want);
check(h.size() == 0);
long x = 42;
int[] vals = new int[1000];
for (int i = 0; i < 1000; i++) {
x = x * 48271 % 2147483647L;
vals[i] = (int) (x % 1000);
}
for (int v : vals) h.push(v);
int[] sorted = vals.clone();
Arrays.sort(sorted);
for (int want : sorted) check(h.pop() == want);
BinaryHeap<Integer> max = new BinaryHeap<>(Comparator.reverseOrder()); // max-heap for free
for (int v : vals) max.push(v);
check(max.pop() == sorted[999]);
System.out.println("ok");
}
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <stdexcept>
#include <utility>
#include <vector>
// Array-backed binary heap. Less = std::less gives a min-heap, std::greater a max-heap.
template <class T, class Less = std::less<T>>
class BinaryHeap {
public:
std::size_t size() const { return a_.size(); }
const T& peek() const {
if (a_.empty()) throw std::out_of_range("empty heap");
return a_.front();
}
void push(T x) {
a_.push_back(std::move(x));
std::size_t i = a_.size() - 1;
while (i > 0) { // sift-up
std::size_t p = (i - 1) / 2;
if (!less_(a_[i], a_[p])) break;
std::swap(a_[i], a_[p]);
i = p;
}
}
T pop() {
if (a_.empty()) throw std::out_of_range("empty heap");
T top = std::move(a_.front());
a_.front() = std::move(a_.back());
a_.pop_back();
std::size_t i = 0, n = a_.size();
while (true) { // sift-down
std::size_t l = 2 * i + 1, r = l + 1, s = i;
if (l < n && less_(a_[l], a_[s])) s = l;
if (r < n && less_(a_[r], a_[s])) s = r;
if (s == i) break;
std::swap(a_[i], a_[s]);
i = s;
}
return top;
}
const std::vector<T>& raw() const { return a_; }
private:
std::vector<T> a_;
Less less_{};
};
int main() {
BinaryHeap<int> h;
for (int x : {5, 3, 8, 1, 9, 2}) h.push(x);
assert((h.raw() == std::vector<int>{1, 3, 2, 5, 9, 8}) && h.peek() == 1);
assert(h.pop() == 1 && h.pop() == 2);
assert((h.raw() == std::vector<int>{3, 5, 8, 9}));
for (int want : {3, 5, 8, 9}) assert(h.pop() == want);
assert(h.size() == 0);
std::int64_t x = 42;
std::vector<int> vals;
for (int i = 0; i < 1000; i++) {
x = x * 48271 % 2147483647;
vals.push_back(static_cast<int>(x % 1000));
}
for (int v : vals) h.push(v);
std::vector<int> sorted = vals;
std::sort(sorted.begin(), sorted.end());
for (int want : sorted) assert(h.pop() == want);
BinaryHeap<int, std::greater<int>> mx; // max-heap for free
for (int v : vals) mx.push(v);
assert(mx.pop() == sorted.back());
std::cout << "ok\n";
}
class MinHeap {
private heap: number[] = [];
get size(): number {
return this.heap.length;
}
peek(): number | undefined {
return this.heap[0];
}
push(val: number): void {
this.heap.push(val);
this.bubbleUp(this.heap.length - 1);
}
pop(): number | undefined {
if (this.heap.length === 0) return undefined;
const min = this.heap[0];
const last = this.heap.pop()!;
if (this.heap.length > 0) {
this.heap[0] = last;
this.bubbleDown(0);
}
return min;
}
private bubbleUp(idx: number): void {
while (idx > 0) {
const parent = Math.floor((idx - 1) / 2);
if (this.heap[parent] <= this.heap[idx]) break;
[this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
idx = parent;
}
}
private bubbleDown(idx: number): void {
const n = this.heap.length;
while (true) {
let smallest = idx;
const left = 2 * idx + 1;
const right = 2 * idx + 2;
if (left < n && this.heap[left] < this.heap[smallest]) smallest = left;
if (right < n && this.heap[right] < this.heap[smallest]) smallest = right;
if (smallest === idx) break;
[this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
idx = smallest;
}
}
}
// --- shared test (identical in all four languages) ---
const h = new MinHeap();
const raw = () => (h as unknown as { heap: number[] }).heap.join(",");
for (const x of [5, 3, 8, 1, 9, 2]) h.push(x);
if (raw() !== "1,3,2,5,9,8" || h.peek() !== 1) throw new Error("push trace");
if (h.pop() !== 1 || h.pop() !== 2) throw new Error("pop trace");
if (raw() !== "3,5,8,9") throw new Error("after pops");
for (const want of [3, 5, 8, 9]) if (h.pop() !== want) throw new Error("drain");
if (h.size !== 0 || h.pop() !== undefined) throw new Error("empty");
let x = 42;
const vals: number[] = [];
for (let i = 0; i < 1000; i++) {
x = (x * 48271) % 2147483647; // products stay below 2^53: exact in doubles
vals.push(x % 1000);
}
for (const v of vals) h.push(v);
const sorted = [...vals].sort((a, b) => a - b);
for (const want of sorted) if (h.pop() !== want) throw new Error("random");
console.log("ok");
Two small differences between the versions are worth noticing. The Python pop raises IndexError on an empty heap (via self.heap[0]) while TypeScript returns undefined; pick one convention for your codebase. And the Python pop special-cases size 1 because self.heap[0] = self.heap.pop() would otherwise write the popped element back into the now-empty list; the Java and C++ versions handle it by checking emptiness after removing the last element.
Python's heapq
In practice, use Python's built-in heapq module — it's a min-heap implemented in C, much faster than a pure Python implementation.
import heapq
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
smallest = heapq.heappop(heap) # 2
# For a max-heap, negate values:
heapq.heappush(heap, -10) # pushes 10 as max
largest = -heapq.heappop(heap) # 10
Two heapq functions people forget: heapq.heapreplace(h, x) pops the smallest and pushes x with a single sift-down (cheaper than pop then push), and heapq.heappushpop(h, x) pushes then pops, returning x immediately if it is not larger than the root — exactly what a bounded top-K heap needs. Python 3.14 added public max-heap variants (heapq.heappush_max, heapq.heappop_max and friends); on older versions negate the keys, or wrap non-numeric items in a class with an inverted __lt__. In Java, new PriorityQueue<>(Comparator.reverseOrder()) is a max-heap; in C++, std::priority_queue<int> is already a max-heap and std::priority_queue<int, std::vector<int>, std::greater<int>> is a min-heap — the opposite default from Python and Java, and a frequent source of bugs.
Build Heap — Why ?
Building a heap by inserting elements one by one is . But building bottom-up (heapifying from the last non-leaf to the root) is .
Intuition: Most nodes are near the bottom of the tree and only need to bubble down a few levels. The sum of work across all levels is:
Python:
def build_heap(arr: list[int]) -> None:
"""In-place heapify. O(n) time."""
n = len(arr)
# Start from last non-leaf node
for i in range(n // 2 - 1, -1, -1):
heapify_down(arr, n, i)
def heapify_down(arr: list[int], size: int, idx: int) -> None:
smallest = idx
left = 2 * idx + 1
right = 2 * idx + 2
if left < size and arr[left] < arr[smallest]:
smallest = left
if right < size and arr[right] < arr[smallest]:
smallest = right
if smallest != idx:
arr[idx], arr[smallest] = arr[smallest], arr[idx]
heapify_down(arr, size, smallest)
The exact proof: sum of heights
The bound above uses the CLRS counting argument (at most nodes have height ). There is a cleaner exact statement.
Claim. Sift-down from node performs at most swaps, so bottom-up heapify performs at most swaps. For a perfect tree with nodes, ; for every , .
Proof for the perfect tree. Level has nodes, each of height . So
Substitute : . Using , we get . ∎
A rigorous bound for any . A heap with nodes and height sits inside the perfect tree of height , and every node's height is at most its height in that perfect tree. The perfect tree has nodes (because ), so . That already proves heapify is : at most swaps and comparisons.
The exact value. In fact , where is the number of 1-bits in the binary representation of ; in particular . We did not derive this identity on the page; a script confirmed it for every from 1 to 4,096 and for , and (for example ). Since each swap costs two comparisons, heapify does fewer than comparisons. Concrete numbers on the worst input for a min-heap (strictly decreasing values, ):
| Build method | Swaps | Comparisons | Bound |
|---|---|---|---|
| Bottom-up heapify (Floyd) | 1,048,555 ( with ) | 2,097,110 | |
| Insert one at a time (sift-up each) | 18,874,370 | about the same as swaps |
Why the asymmetry? Sift-down moves an element a distance equal to its height, and most nodes are near the bottom (small height). Sift-up moves an element a distance equal to its depth, and most nodes are near the bottom (large depth). Same tree, opposite weighting. Insert-one-at-a-time on decreasing input makes every new element travel all the way to the root.
Trace: heapify [3, 1, 6, 5, 2, 4]
Computed by running build_heap with logging. , so the internal nodes are indices 2, 1, 0 and they are processed in that order.
| Start index | Swaps (i ↔ child) | Array after |
|---|---|---|
| 2 | 2 ↔ 5 | [3, 1, 4, 5, 2, 6] |
| 1 | none | [3, 1, 4, 5, 2, 6] |
| 0 | 0 ↔ 1, then 1 ↔ 4 | [1, 2, 4, 5, 3, 6] |
Three swaps; heapq.heapify produces the same [1, 2, 4, 5, 3, 6]. This is also the answer to Problem 1 in "Try It Yourself" below.
Correctness
The heap operations are short, so their proofs are short — but interviewers ask for them, and the invariants are exactly what you check when a heap bug appears.
Heap property (min-heap): for every , . By transitivity, the root is the minimum: every node is reached from the root by a chain of non-decreasing values.
Sift-up invariant. Before each iteration with current index : the array satisfies the heap property everywhere except possibly between and its parent; moreover, if has a parent and children, then each child of . Initialisation: only the new leaf can be out of place, and it has no children. Maintenance: if we swap. The old moves down to ; it was ≤ 's children before (the "moreover" clause), so the edges below are fine; the new is smaller than the old one, so it is still ≤ 's other child. The only possible violation has moved up to , and the clause holds there because the old old , which bounds both of 's current children. Termination: we stop when (no violation left) or (no parent). At most iterations.
Sift-down invariant. Before each iteration with current index : the heap property holds everywhere except possibly between and its children; and each child of . Swapping with its smaller child puts old at . It is ≤ the other child (it was the smaller one) and ≤ the old now at (that is why we swapped), so both edges below hold. It is ≥ by the second clause of the invariant, so the edge above holds too. The only possible violation has moved down to , and the second clause holds there: the new parent of is old , which was ≤ both of 's children before the swap because the heap property held below . The loop stops at a leaf or when both children.
Heapify loop invariant (CLRS §6.3). At the start of the iteration for index , every node is the root of a valid heap. Initially all are leaves, which are trivially heaps. Sift-down at , whose two subtrees are heaps by the invariant, makes the subtree at a heap. When the loop ends at , node 0 is the root of a heap.
Pop is correct because removing the root and moving the last element to index 0 leaves a complete tree whose only possible violation is at the root — exactly the precondition of sift-down.
Top-K Problems
Kth Largest Element
Use a min-heap of size K. After processing all elements, the root is the Kth largest.
TypeScript:
function findKthLargest(nums: number[], k: number): number {
const heap = new MinHeap();
for (const num of nums) {
heap.push(num);
if (heap.size > k) {
heap.pop(); // remove smallest — keeps K largest
}
}
return heap.peek()!;
}
Python:
import heapq
def find_kth_largest(nums: list[int], k: int) -> int:
# nlargest is optimized for this exact use case
return heapq.nlargest(k, nums)[-1]
# Or manually with a min-heap of size k:
# heap = []
# for num in nums:
# heapq.heappush(heap, num)
# if len(heap) > k:
# heapq.heappop(heap)
# return heap[0]
Complexity: time, space. When , this is much better than sorting ().
Why a min-heap for the largest: the heap holds the best candidates seen so far, and the question at each new element is "does it beat the worst of my current top ?" The worst of the top is the smallest, so it must be at the root. The invariant — the heap contains the largest elements of the prefix processed so far — is preserved because a new element enters only by evicting the current -th largest, which can no longer be in the top .
Heap of size k vs quickselect vs sort
| Approach | Time | Extra space | Works on a stream? | Output |
|---|---|---|---|---|
| Sort, take | or in place | No | Top sorted | |
| Bounded heap of size | Yes | Top unsorted ( to sort) | ||
| Heapify all, pop times | in place | No | Top sorted | |
| Quickselect | expected, worst | in place (mutates) | No | -th element plus an unsorted partition |
| Median of medians / introselect | worst | in place | No | Same as quickselect |
The rule of thumb: online or memory-bounded → heap; offline, one query, mutation allowed → quickselect (Quickselect, Median of Medians & Order Statistics). C++'s std::nth_element is introselect (quickselect with a fallback), and std::partial_sort is heap-based: it builds a heap of the first elements and streams the rest through it, . Python's heapq.nlargest(k, it) uses the bounded-heap approach and falls back to sorted (or max) when that is cheaper, per its documentation. Heap sort itself — heapify then pop everything — is covered in Heap Sort.
Top-K Frequent Elements
Python:
from collections import Counter
import heapq
def top_k_frequent(nums: list[int], k: int) -> list[int]:
count = Counter(nums)
# Use a min-heap of size k based on frequency
return heapq.nlargest(k, count.keys(), key=count.get)
TypeScript:
function topKFrequent(nums: number[], k: number): number[] {
const freq = new Map<number, number>();
for (const num of nums) {
freq.set(num, (freq.get(num) || 0) + 1);
}
// Bucket sort approach — O(n)
const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
for (const [num, count] of freq) {
buckets[count].push(num);
}
const result: number[] = [];
for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
result.push(...buckets[i]);
}
return result.slice(0, k);
}
The two versions show the real trade-off: the heap is for distinct values and works for any key; the bucket version is but only because frequencies are integers bounded by . For a stream of frequencies that keep changing (a "trending now" list), neither is enough; production systems use approximate structures such as Count-Min Sketch plus a small heap (Bloom Filters, Count-Min Sketch & Probabilistic Structures).
Median Finding (Two Heaps)
Maintain a max-heap for the lower half and a min-heap for the upper half. The median is always at the top of one or both heaps.
graph LR
subgraph "Max-Heap (lower half)"
A["3"] --- B["2"]
A --- C["1"]
end
subgraph "Min-Heap (upper half)"
D["4"] --- E["5"]
D --- F["7"]
end
A -->|"median = (3+4)/2 = 3.5"| D
The two invariants: (1) order — every element of lo is ≤ every element of hi, i.e. max(lo) <= min(hi); (2) size — len(lo) == len(hi) or len(lo) == len(hi) + 1. Given both, the median is max(lo) for odd counts and the mean of the two tops for even counts, because lo holds exactly the lower elements. The "push into lo, move lo's max to hi, move back if hi got bigger" sequence below restores both invariants with at most three heap operations, each : routing every new element through lo first guarantees the element that lands in hi is the largest of the lower side, so order holds; the final move fixes size.
All four versions run the same test: the stream 5, 15, 1, 3 (medians 5, 10, 5, 4), then 301 MINSTD values checked against a sorted-list median after every insertion.
import heapq
class MedianFinder:
def __init__(self):
self.max_heap: list[int] = [] # lower half (negated)
self.min_heap: list[int] = [] # upper half
def add_num(self, num: int) -> None:
heapq.heappush(self.max_heap, -num)
heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
if len(self.min_heap) > len(self.max_heap):
heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
def find_median(self) -> float:
if len(self.max_heap) > len(self.min_heap):
return -self.max_heap[0]
return (-self.max_heap[0] + self.min_heap[0]) / 2
# --- shared test ---
import bisect
mf = MedianFinder()
got = []
for v in [5, 15, 1, 3]:
mf.add_num(v)
got.append(mf.find_median())
assert got == [5, 10, 5, 4]
mf, seen, x = MedianFinder(), [], 42
for _ in range(301):
x = x * 48271 % 2147483647
v = x % 1000
mf.add_num(v)
bisect.insort(seen, v)
n = len(seen)
want = seen[n // 2] if n % 2 else (seen[n // 2 - 1] + seen[n // 2]) / 2
assert mf.find_median() == want
print("ok")
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
public class MedianFinderDemo {
static final class MedianFinder {
private final PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
private final PriorityQueue<Integer> hi = new PriorityQueue<>(); // min-heap
void addNum(int num) {
lo.add(num);
hi.add(lo.poll()); // largest of the low side crosses over
if (hi.size() > lo.size()) lo.add(hi.poll());
}
double findMedian() {
if (lo.size() > hi.size()) return lo.peek();
return ((long) lo.peek() + hi.peek()) / 2.0; // long: no int overflow
}
}
static void check(boolean cond) { if (!cond) throw new AssertionError(); }
public static void main(String[] args) {
MedianFinder mf = new MedianFinder();
double[] want = {5, 10, 5, 4};
int[] stream = {5, 15, 1, 3};
for (int i = 0; i < 4; i++) {
mf.addNum(stream[i]);
check(mf.findMedian() == want[i]);
}
mf = new MedianFinder();
List<Integer> seen = new ArrayList<>();
long x = 42;
for (int i = 0; i < 301; i++) {
x = x * 48271 % 2147483647L;
int v = (int) (x % 1000);
mf.addNum(v);
int pos = Collections.binarySearch(seen, v);
seen.add(pos < 0 ? -pos - 1 : pos, v);
int n = seen.size();
double w = n % 2 == 1 ? seen.get(n / 2) : (seen.get(n / 2 - 1) + seen.get(n / 2)) / 2.0;
check(mf.findMedian() == w);
}
System.out.println("ok");
}
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
class MedianFinder {
public:
void addNum(int num) {
lo_.push(num);
hi_.push(lo_.top()); // largest of the low side crosses over
lo_.pop();
if (hi_.size() > lo_.size()) {
lo_.push(hi_.top());
hi_.pop();
}
}
double findMedian() const {
if (lo_.size() > hi_.size()) return lo_.top();
return (static_cast<std::int64_t>(lo_.top()) + hi_.top()) / 2.0;
}
private:
std::priority_queue<int> lo_; // max-heap (C++ default)
std::priority_queue<int, std::vector<int>, std::greater<int>> hi_; // min-heap
};
int main() {
MedianFinder mf;
const int stream[] = {5, 15, 1, 3};
const double want[] = {5, 10, 5, 4};
for (int i = 0; i < 4; i++) {
mf.addNum(stream[i]);
assert(mf.findMedian() == want[i]);
}
MedianFinder m2;
std::vector<int> seen;
std::int64_t x = 42;
for (int i = 0; i < 301; i++) {
x = x * 48271 % 2147483647;
int v = static_cast<int>(x % 1000);
m2.addNum(v);
seen.insert(std::upper_bound(seen.begin(), seen.end(), v), v);
std::size_t n = seen.size();
double w = n % 2 ? seen[n / 2] : (seen[n / 2 - 1] + seen[n / 2]) / 2.0;
assert(m2.findMedian() == w);
}
std::cout << "ok\n";
}
class MedianFinder {
private maxHeap: number[] = []; // lower half (negate for max behavior)
private minHeap: number[] = []; // upper half
addNum(num: number): void {
// Always add to maxHeap first (store as negated)
this.heapPush(this.maxHeap, -num);
// Balance: max of lower half should be <= min of upper half
this.heapPush(this.minHeap, -this.heapPop(this.maxHeap)!);
// Keep sizes balanced (maxHeap can be 1 larger)
if (this.minHeap.length > this.maxHeap.length) {
this.heapPush(this.maxHeap, -this.heapPop(this.minHeap)!);
}
}
findMedian(): number {
if (this.maxHeap.length > this.minHeap.length) {
return -this.maxHeap[0];
}
return (-this.maxHeap[0] + this.minHeap[0]) / 2;
}
private heapPush(heap: number[], val: number): void {
heap.push(val);
let i = heap.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (heap[parent] <= heap[i]) break;
[heap[parent], heap[i]] = [heap[i], heap[parent]];
i = parent;
}
}
private heapPop(heap: number[]): number | undefined {
if (heap.length === 0) return undefined;
const top = heap[0];
const last = heap.pop()!;
if (heap.length > 0) {
heap[0] = last;
let i = 0;
while (true) {
let smallest = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < heap.length && heap[l] < heap[smallest]) smallest = l;
if (r < heap.length && heap[r] < heap[smallest]) smallest = r;
if (smallest === i) break;
[heap[i], heap[smallest]] = [heap[smallest], heap[i]];
i = smallest;
}
}
return top;
}
}
// --- shared test ---
let mf = new MedianFinder();
const got: number[] = [];
for (const v of [5, 15, 1, 3]) {
mf.addNum(v);
got.push(mf.findMedian());
}
if (got.join(",") !== "5,10,5,4") throw new Error("small stream " + got);
mf = new MedianFinder();
const seen: number[] = [];
let x = 42;
for (let i = 0; i < 301; i++) {
x = (x * 48271) % 2147483647;
const v = x % 1000;
mf.addNum(v);
let pos = seen.findIndex((s) => s > v);
if (pos < 0) pos = seen.length;
seen.splice(pos, 0, v);
const n = seen.length;
const want = n % 2 ? seen[n >> 1] : (seen[n / 2 - 1] + seen[n / 2]) / 2;
if (mf.findMedian() !== want) throw new Error("median mismatch at " + i);
}
console.log("ok");
Complexity: per insertion, for median query.
The TypeScript version negates values to reuse one min-heap routine for both halves. Negation is safe for JavaScript numbers in the integer range, but in Java or C++ negating Integer.MIN_VALUE / INT_MIN overflows back to itself, which is why the Java and C++ versions use a reversed comparator instead.
Sliding window median: two heaps with lazy deletion
Now the window slides: each step adds one element and removes an old one. Binary heaps cannot delete an arbitrary element cheaply (finding it is ). The lazy deletion trick: record the element in a delayed counter instead of removing it, keep a count of live elements per heap, and discard delayed elements only when they reach a heap's top (where removal is a normal pop). The invariant to protect is "both tops are live" — then every comparison and the median read only see real elements. Dead entries buried inside a heap are harmless; they cost memory, bounded by the number of operations since they were added.
import heapq
from collections import defaultdict
def median_sliding_window(nums, k):
lo, hi = [], [] # lo: max-heap via negation, hi: min-heap
delayed = defaultdict(int) # value -> number of pending deletions
lo_size = hi_size = 0 # live counts
def prune(heap, sign): # pop dead entries off the top
while heap and delayed[sign * heap[0]]:
delayed[sign * heap[0]] -= 1
heapq.heappop(heap)
def rebalance():
nonlocal lo_size, hi_size
if lo_size > hi_size + 1:
heapq.heappush(hi, -heapq.heappop(lo))
lo_size, hi_size = lo_size - 1, hi_size + 1
prune(lo, -1)
elif lo_size < hi_size:
heapq.heappush(lo, -heapq.heappop(hi))
lo_size, hi_size = lo_size + 1, hi_size - 1
prune(hi, 1)
def add(x):
nonlocal lo_size, hi_size
if not lo or x <= -lo[0]:
heapq.heappush(lo, -x)
lo_size += 1
else:
heapq.heappush(hi, x)
hi_size += 1
rebalance()
def remove(x):
nonlocal lo_size, hi_size
delayed[x] += 1
if x <= -lo[0]: # x lives in the low half
lo_size -= 1
if x == -lo[0]:
prune(lo, -1)
else:
hi_size -= 1
if hi and x == hi[0]:
prune(hi, 1)
rebalance()
def median():
return float(-lo[0]) if k % 2 else (-lo[0] + hi[0]) / 2
out = []
for i, x in enumerate(nums):
add(x)
if i >= k:
remove(nums[i - k])
if i >= k - 1:
out.append(median())
return out
def brute(nums, k):
res = []
for i in range(len(nums) - k + 1):
w = sorted(nums[i:i + k])
res.append(float(w[k // 2]) if k % 2 else (w[k // 2 - 1] + w[k // 2]) / 2)
return res
assert median_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3) == [1, -1, -1, 3, 5, 6]
assert median_sliding_window([1, 2, 3, 4, 2, 3, 1, 4, 2], 3) == [2, 3, 3, 3, 2, 3, 2]
x, data = 42, []
for _ in range(400):
x = x * 48271 % 2147483647
data.append(x % 20 - 10) # many duplicates and negatives
for k in (1, 2, 3, 4, 7, 50):
assert median_sliding_window(data, k) == brute(data, k), k
print("ok")
Each element is pushed once and popped at most once (either as a move between heaps or as a pruned dead entry), so the total is time — strictly, rather than , because dead entries can make a heap larger than . Space is in the worst case for the same reason. A balanced BST or an order-statistic structure (two SortedLists, a TreeMap with counts, or a Fenwick tree over compressed values) gives a clean with true deletion; the two-heap version is what interviewers expect to see because it builds on the stream median.
Priority Queue Applications
Task Scheduling
Process tasks by priority, not arrival order.
Python:
import heapq
from dataclasses import dataclass, field
@dataclass(order=True)
class Task:
priority: int
name: str = field(compare=False)
class TaskScheduler:
def __init__(self):
self.queue: list[Task] = []
def add_task(self, name: str, priority: int) -> None:
heapq.heappush(self.queue, Task(priority, name))
def get_next(self) -> str | None:
if self.queue:
return heapq.heappop(self.queue).name
return None
This scheduler is not FIFO among equal priorities: a binary heap is not stable, so two tasks with priority 1 may come out in either order. If arrival order matters, add a monotonically increasing sequence number as a tie-breaker — (priority, seq, task) — which is exactly what the heapq documentation recommends; it also prevents Python from ever comparing two task objects that have no ordering.
Meeting rooms and the "minimum resources" pattern
"Given meeting intervals, how many rooms are needed?" Sort meetings by start time and keep a min-heap of end times of the meetings currently occupying rooms. For each meeting, if the earliest-ending room is free (heap[0] <= start), reuse it (heapreplace); otherwise open a new room (heappush). The heap's maximum size is the answer, which equals the maximum number of intervals overlapping any point (the depth); the sweep-line proof that depth is both necessary and sufficient is in Intervals: Merge, Insert, Sweep Line & Scheduling.
import heapq
def min_meeting_rooms(intervals):
ends = [] # end times of occupied rooms
for start, end in sorted(intervals):
if ends and ends[0] <= start:
heapq.heapreplace(ends, end) # reuse the room that frees up first
else:
heapq.heappush(ends, end) # need another room
return len(ends)
assert min_meeting_rooms([(0, 30), (5, 10), (15, 20)]) == 2
assert min_meeting_rooms([(7, 10), (2, 4)]) == 1
assert min_meeting_rooms([(1, 5), (2, 6), (3, 7), (5, 8)]) == 3 # [5,8) reuses the room freed at 5
assert min_meeting_rooms([]) == 0
print("ok")
The same skeleton — sort by availability, heap of whatever frees up next — solves "minimum platforms", "car pooling" variants, "process tasks on k servers" (LeetCode 1882), and Meeting Rooms III (LeetCode 2402), which needs two heaps: free rooms by number, busy rooms by end time. CPU scheduling with a cooldown (LeetCode 621, Task Scheduler) uses a max-heap of remaining counts plus a queue of tasks cooling down.
Merge K Sorted Streams
Merge K sorted iterators into a single sorted stream — used in database merge operations, log aggregation, and external sorting.
Python:
import heapq
from typing import Iterator
def merge_k_sorted(streams: list[Iterator[int]]) -> Iterator[int]:
heap = []
for i, stream in enumerate(streams):
try:
val = next(stream)
heapq.heappush(heap, (val, i))
except StopIteration:
pass
while heap:
val, i = heapq.heappop(heap)
yield val
try:
next_val = next(streams[i])
heapq.heappush(heap, (next_val, i))
except StopIteration:
pass
Production Use Case
This pattern is how Kafka consumers merge partitions, how databases merge sorted runs during compaction, and how log aggregation systems combine logs from multiple sources. The complexity makes it efficient even with hundreds of streams.
Correction: Kafka consumers do not k-way merge partitions
Kafka guarantees order only within a partition. A consumer that reads several partitions receives batches from each in whatever order the fetches return; it does not merge them into one globally ordered stream, and there is no global order to merge by. (A stream processor that needs event-time order across partitions, such as Kafka Streams, buffers and aligns by timestamp, which is a different mechanism.) The other two examples are accurate: LSM-tree stores such as RocksDB merge sorted runs during compaction with a heap-based merging iterator, and log aggregators that combine per-host sorted logs do a k-way merge. External sorting is the textbook case (see Storage Engines).
Why . The heap never holds more than one entry per stream, so its size is at most . Each of the output elements costs one pop and at most one push, each. Space is beyond the output — which is why the k-way merge is the core of external sorting: with runs on disk and room in memory for only one buffer per run, you can merge arbitrarily large files. Python ships this as heapq.merge(*iterables). The (val, i) tuple doubles as a tie-breaker: equal values compare by stream index, so the merge is stable with respect to stream order and never compares the streams themselves.
The linked-list form (LeetCode 23) is the same algorithm with list nodes instead of iterators; its solution is in the practice ladder. The alternative without a heap — merge the lists pairwise like the levels of merge sort — is also (Merge Sort); merging them one at a time into an accumulator is , the brute force interviewers want you to beat.
Smallest range covering one element from each list
A k-way merge variant that shows why the heap's contents, not just its top, matter. Keep one pointer per list in a min-heap and track the current maximum of the pointed-to values separately. The heap top is the current minimum, so [min, max] is a range covering one element from every list. To try to shrink it, the only useful move is to advance the list holding the minimum (advancing any other list can only raise the maximum). Stop when that list is exhausted — no further range can cover it.
import heapq
def smallest_range(lists):
heap = [(lst[0], i, 0) for i, lst in enumerate(lists)]
heapq.heapify(heap)
cur_max = max(lst[0] for lst in lists)
best = (heap[0][0], cur_max)
while True:
lo, i, j = heapq.heappop(heap)
if cur_max - lo < best[1] - best[0]:
best = (lo, cur_max)
if j + 1 == len(lists[i]):
return list(best)
nxt = lists[i][j + 1]
cur_max = max(cur_max, nxt)
heapq.heappush(heap, (nxt, i, j + 1))
assert smallest_range([[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]) == [20, 24]
assert smallest_range([[1, 2, 3], [1, 2, 3], [1, 2, 3]]) == [1, 1]
assert smallest_range([[10], [11]]) == [10, 11]
print("ok")
time for total elements and lists, space. Ties are resolved toward the earlier (smaller-start) range because the comparison is strict and candidates appear in increasing order of lo.
Dijkstra's Algorithm
The priority queue is the heart of Dijkstra. See Graphs: Dijkstra for the full implementation.
Decrease-key, and why library heaps do not have it
Textbook Dijkstra and Prim call decrease-key: "vertex is already in the queue with priority 12; its priority is now 7." In a binary heap the operation itself is easy — set the new key and sift up, — but you need to know where is in the array, and positions change on every swap. Supporting it requires a position map (qp[v] = index of in the heap) that every swap keeps up to date. That is what the IndexedMinPQ in the next section does, and it is why the standard library heaps leave it out:
- Python
heapqworks on a plain list of arbitrary items and has no notion of identity, so it cannot offer decrease-key. Its documentation instead recommends marking entries as removed and pushing a new entry (lazy deletion). - Java
PriorityQueuehasremove(Object), but it is a linear scan, , per the Javadoc. No handles, no decrease-key. - C++
std::priority_queueexposes onlypush,pop,top. Boost.Heap provides "mutable" heaps (d-ary, binomial, Fibonacci, pairing) that return a handle frompushand supportupdate/decrease. - Go
container/heapis the exception: it is a set of functions over your own type, andheap.Fix(h, i)re-establishes order after you change the element at indexi. To use it as decrease-key you must store each element's index and update it in yourSwapmethod — the position map, written by you.
The handle-free alternative is lazy deletion: never decrease a key; push a new entry (new_dist, v) and leave the old one in the heap. When an entry is popped, check whether it is stale (d > dist[v]) and skip it if so. The heap now holds up to one entry per edge relaxation instead of one per vertex, so its size is rather than , and each operation costs . Total: — the same bound as decrease-key with a binary heap, with simpler code and better constants.
import heapq
def dijkstra(n, edges, src):
graph = [[] for _ in range(n)]
for u, v, w in edges:
graph[u].append((v, w))
dist = [float("inf")] * n
dist[src] = 0
pq = [(0, src)]
pops = stale = 0
while pq:
d, u = heapq.heappop(pq)
pops += 1
if d > dist[u]: # stale entry: u was settled with a smaller distance
stale += 1
continue
for v, w in graph[u]:
nd = d + w
if nd < dist[v]: # "decrease-key" = push a fresh entry
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist, pops, stale
def bellman_ford(n, edges, src): # brute-force check
dist = [float("inf")] * n
dist[src] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return dist
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3)]
dist, pops, stale = dijkstra(5, edges, 0)
assert dist == [0, 3, 1, 4, 7]
assert stale == 2 and pops == 7 # vertices 1 and 3 were each pushed twice
x, rnd = 42, []
for _ in range(600):
x = x * 48271 % 2147483647
rnd.append((x % 60, (x >> 8) % 60, (x >> 16) % 50))
assert dijkstra(60, rnd, 0)[0] == bellman_ford(60, rnd, 0)
print("ok")
In the small graph, vertex 1 is first reached with distance 4 (directly from 0) and then improved to 3 (via 2); the old (4, 1) entry stays in the heap and is skipped when popped. The same happens to vertex 3 (first 6 via vertex 2, then 4 via vertex 1). Logged pop order: (0,0) (1,2) (3,1) (4,1) stale, (4,3) (6,3) stale, (7,4) — 7 pops for 5 vertices, 2 of them stale. Lazy deletion is also how you implement "cancel" for timers and "remove" for the sliding-window median: mark, and let the top-of-heap check do the actual removal. Its cost is memory proportional to the number of stale entries; if cancellations dominate (a server cancelling most of its timeouts), periodically rebuild the heap from the live entries in .
Heap vs Other Data Structures
| Need | Use | Why |
|---|---|---|
| Get min/max quickly | Heap | peek |
| Get min/max AND search | Balanced BST | for all operations |
| Get min/max AND rank queries | Balanced BST or Segment Tree | Heap doesn't support rank |
| Sort partially (Top-K) | Heap of size K | vs |
| FIFO with priority | Priority queue (heap) | Natural fit |
| Median maintenance | Two heaps | insert, query |
Common Mistake
A heap does not store elements in sorted order. The heap property only guarantees the root is the min/max. The internal order is not fully sorted — iterating over the heap array does not give sorted output. To extract all elements in sorted order, you must pop times: .
Advanced: Indexed Priority Queue
An indexed priority queue allows updating the priority of an existing element in . This is essential for Dijkstra's algorithm with decrease-key operations and for scheduling systems where priorities change.
Python (simplified):
class IndexedMinPQ:
def __init__(self, max_size: int):
self.max_size = max_size
self.n = 0
self.keys: list[float | None] = [None] * max_size
self.pq = [0] * (max_size + 1) # binary heap
self.qp = [-1] * max_size # inverse: qp[i] = position of i in pq
def contains(self, i: int) -> bool:
return self.qp[i] != -1
def insert(self, i: int, key: float) -> None:
self.n += 1
self.qp[i] = self.n
self.pq[self.n] = i
self.keys[i] = key
self._swim(self.n)
def decrease_key(self, i: int, key: float) -> None:
self.keys[i] = key
self._swim(self.qp[i])
def pop_min(self) -> int:
min_idx = self.pq[1]
self._swap(1, self.n)
self.n -= 1
self._sink(1)
self.qp[min_idx] = -1
self.keys[min_idx] = None
return min_idx
def _swim(self, k: int) -> None:
while k > 1 and self.keys[self.pq[k // 2]] > self.keys[self.pq[k]]:
self._swap(k, k // 2)
k //= 2
def _sink(self, k: int) -> None:
while 2 * k <= self.n:
j = 2 * k
if j < self.n and self.keys[self.pq[j + 1]] < self.keys[self.pq[j]]:
j += 1
if self.keys[self.pq[k]] <= self.keys[self.pq[j]]:
break
self._swap(k, j)
k = j
def _swap(self, i: int, j: int) -> None:
self.pq[i], self.pq[j] = self.pq[j], self.pq[i]
self.qp[self.pq[i]] = i
self.qp[self.pq[j]] = j
This is Sedgewick and Wayne's IndexMinPQ (Algorithms, §2.4), 1-indexed: pq is the heap of item ids, qp its inverse, and keys the priorities by id. The invariant pq[qp[i]] == i for every contained i is maintained by _swap, which is why every movement goes through it. decrease_key only swims: a smaller key can only violate the edge to the parent. An increase_key would sink instead, and a general change_key does both (one of them is a no-op). With vertices this gives Dijkstra an -sized heap and the textbook bound.
Beyond binary heaps
d-ary heaps
A d-ary heap gives every node children (children of at ; parent ). The height drops to : for that is 19 levels for , 13 for , 10 for , 7 for and 5 for (computed).
- Sift-up gets cheaper: one comparison per level and fewer levels, .
- Sift-down gets more expensive per level: choose the smallest of children, comparisons per level, total. For that is comparisons — the same as a binary heap's 2 per level — but over half as many levels.
- Cache behaviour is the real win. The children of a node are contiguous in the array. With 8-byte keys, four children occupy 32 bytes, half a 64-byte cache line, so examining all of them usually costs one cache miss, whereas a binary heap spends one potential miss per level on twice as many levels. Once the heap no longer fits in cache, levels are what you pay for.
That is why is the common practical choice: Go's runtime keeps each P's timers in a 4-ary heap (timerHeapN = 4 in runtime/time.go), and Boost.Heap offers d_ary_heap with arity as a parameter. Johnson (1975) introduced d-ary heaps for Dijkstra: with , decrease-key (a sift-up) costs and the total becomes , which is for dense graphs. Heaps used mostly for push/decrease-key (Dijkstra on dense graphs) want a larger ; heaps dominated by pop want around 4.
Binomial, Fibonacci and pairing heaps
Binary heaps cannot meld (merge two heaps) faster than , and decrease-key is . Pointer-based heaps relax the "one complete tree" shape to fix that.
- A binomial heap (Vuillemin, 1978) is a forest of binomial trees, at most one of each size , like the binary representation of . Melding is binary addition with carries, ; insert is amortized.
- A Fibonacci heap (Fredman and Tarjan, "Fibonacci heaps and their uses in improved network optimization algorithms", Journal of the ACM 34(3), 1987) is lazier still: insert and meld just add trees to a root list, decrease-key cuts the node out and adds it as a new root (with "cascading cuts" marking parents that lost a child), and all the consolidation work is deferred to delete-min. A potential-function analysis gives amortized insert, meld and decrease-key and amortized delete-min. Plugged into Dijkstra this yields , and into Prim's algorithm the same — the bounds that made the paper famous. The name comes from the proof that a node of degree has at least descendants.
- A pairing heap (Fredman, Sedgewick, Sleator and Tarjan, 1986) is a single multiway tree with a "pair up the children, then combine right to left" delete-min. It is simple and fast in practice. Its exact decrease-key complexity is a famous open problem: Fredman (1999) proved it cannot be amortized in general ( lower bound for a broad class), and Pettie (2005) proved an upper bound, which is .
| Operation | Binary heap | 4-ary heap | Binomial heap | Fibonacci heap (amortized) | Pairing heap (amortized) |
|---|---|---|---|---|---|
| insert | amortized, worst | ||||
| find-min | with a min pointer | ||||
| delete-min | |||||
| decrease-key (with handle) | , not | ||||
| meld | |||||
| Dijkstra total | between the two |
Why Fibonacci heaps are rarely faster in practice
The decrease-key only pays off when decrease-keys vastly outnumber delete-mins and the heap is large. In real graphs, is often only a small multiple of , so and differ by a small factor that constants easily erase. Meanwhile each Fibonacci-heap node carries a key, four pointers (parent, child, left and right siblings), a degree and a mark bit, lives at an arbitrary heap address, and delete-min walks a linked root list and consolidates through an auxiliary array — cache misses everywhere. A binary or 4-ary heap is a contiguous array with no pointers at all. Empirical studies agree: Larkin, Sen and Tarjan's "A Back-to-Basics Empirical Study of Priority Queues" (ALENEX 2014) found implicit (array) d-ary heaps and pairing heaps consistently competitive and Fibonacci heaps generally slower. Theoretical alternatives with even better worst-case bounds (Brodal queues, 1996; strict Fibonacci heaps, 2012) are slower still in practice. Use Fibonacci heaps to understand amortized analysis, not to make Dijkstra faster.
Complexity
| Operation | Binary heap | Notes |
|---|---|---|
| push | worst, average for random keys | A random new key rises only about 1.6 levels on average (known result for random insertions; treat the constant as approximate) |
| pop | About comparisons; Floyd's "bottom-up" pop (sift the hole to a leaf, then sift up) cuts this to about | |
| peek | ||
| heapify | , fewer than comparisons | Proof above |
| heapreplace / pushpop | One sift instead of two | |
| decrease-key | with a position map; without | Or lazy deletion: push a duplicate |
| delete arbitrary | with a position map; without | Swap with last, then sift up or down |
| meld | (concatenate and heapify) | Use binomial/pairing/Fibonacci heaps if meld is hot |
| Space | slots, no pointers | Amortized growth as a dynamic array |
On constants and cache behaviour: the top few levels of a heap stay hot in L1 cache, but each deeper level of sift-down touches a new, likely cold, cache line once the heap exceeds cache size. That is the reason for 4-ary heaps and, in extreme cases, for B-heaps and cache-oblivious priority queues, where subtrees are laid out in page-sized blocks (Poul-Henning Kamp's 2010 article "You're Doing It Wrong" in ACM Queue describes a B-heap in the Varnish cache for exactly this reason).
Heaps in real systems
Operating-system and runtime timers. "Which timeout fires next?" is the canonical priority-queue question, and real systems answer it in several ways:
- Go: each P (logical processor) keeps its timers in a 4-ary min-heap keyed by expiry, in the runtime's
time.go. - libuv (the event loop under Node.js): active timers are a binary min-heap (
heap-inl.h). Node.js itself groups JavaScript timers into linked lists by duration and keeps those lists in a binary-heap priority queue keyed by next expiry (lib/internal/timers.js), so thousands ofsetTimeout(fn, 1000)calls cost one heap entry. - Java:
ScheduledThreadPoolExecutoruses an internalDelayedWorkQueue, a binary heap of scheduled tasks;java.util.concurrent.DelayQueuewraps aPriorityQueue. - Linux kernel: not a heap. High-resolution timers (
hrtimer) are kept in a red-black tree with a cached leftmost node (timerqueue), and ordinary low-resolution timeouts live in a hierarchical timer wheel, reworked in Linux 4.8 so that timers are not cascaded between levels. Wheels win when most timers are cancelled before they fire (network retransmit timeouts), because insert and cancel are .
CPU scheduling — a red-black tree, not a heap. It is often said that the Linux scheduler "uses a priority queue". Linux's Completely Fair Scheduler (CFS) kept runnable tasks in a red-black tree ordered by virtual runtime, with the leftmost (smallest vruntime) node cached so picking the next task is and inserting is . Since Linux 6.6 the EEVDF scheduler replaced CFS's policy; it still uses an augmented red-black tree. A tree was chosen over a heap because the scheduler needs arbitrary removal (a task blocks or migrates) and ordered access, not just the minimum. See CPU Scheduling.
Timing wheels as the alternative at scale. Varghese and Lauck's "Hashed and Hierarchical Timing Wheels" (SOSP 1987) replaces the heap with an array of buckets indexed by expiry time modulo the wheel size, giving insert and cancel at the cost of time resolution; hierarchical wheels (like clock hands: seconds, minutes, hours) cover long ranges. Kafka uses hierarchical timing wheels for its "purgatory" of delayed operations (produce requests waiting for acks, fetch requests waiting for data), because it tracks huge numbers of timeouts that are mostly completed early. Its SystemTimer (in the server-common module) combines a TimingWheel with a java.util.concurrent.DelayQueue holding the wheel's buckets — so a heap is still there, but it orders a few hundred bucket expiry times rather than millions of individual requests. Netty's HashedWheelTimer is the same idea for network timeouts.
Discrete-event simulation. A simulator keeps a "future event list" and repeatedly pops the earliest event, which may schedule new events — a pure priority-queue workload. Binary heaps are the default; calendar queues (Brown, CACM 1988), a bucketed structure tuned to the event-time distribution, give expected operations when event times are well spread. The ns-3 network simulator lets you choose among several schedulers (map, list, heap, calendar).
Databases and storage. PostgreSQL's EXPLAIN ANALYZE reports Sort Method: top-N heapsort for ORDER BY ... LIMIT n queries — a bounded heap of size , the top-K pattern exactly — and its external sort merges sorted runs from disk with a heap. LSM-tree engines (RocksDB, LevelDB) use a heap-based merging iterator to combine memtables and SSTables during reads and compaction. See Storage Engines and Query Planning & Optimization.
Networking and graphs. Link-state routing protocols (OSPF, IS-IS) run Dijkstra's shortest-path-first over the topology, with a priority queue at the core (Graphs). Load balancers implementing least-connections or weighted fair queueing keep backends or flows in priority order (Load Balancing Algorithms). Huffman coding (DEFLATE, used by gzip and PNG) builds its code tree by repeatedly merging the two least-frequent symbols from a min-heap. Memory allocators and garbage collectors use heaps for free-block selection in some designs, though the "heap" of dynamic memory is unrelated to the data structure (the shared name is a historical accident).
Pitfalls & edge cases
- Wrong heap direction. Python and Java default to min-heaps; C++'s
std::priority_queuedefaults to a max-heap. Top-K largest needs a min-heap of size ; mixing these up silently returns the k smallest. - Negation overflow. Simulating a max-heap by negating breaks for
Integer.MIN_VALUE/INT_MINand for unsigned types; use a reversed comparator. In Python negation is safe for ints but not for strings or tuples — wrap them. - Comparing payloads on ties.
heapq.heappush(h, (priority, task))raisesTypeErrorwhen two priorities tie andtaskobjects are not orderable (dicts, custom classes). Insert a counter:(priority, next(counter), task). - Assuming stability. Heaps are not stable; equal priorities come out in arbitrary order unless you add a sequence number.
- Iterating the heap array expecting sorted order. Only
heap[0]is meaningful;heap[1]is not the second smallest (it is one of two candidates). - Mutating keys in place. Changing the priority of an object already in a heap breaks the invariant silently; later pops return wrong answers with no error. Remove and re-insert, use a position map, or use lazy deletion.
- Peek/pop on empty. Python raises
IndexError, Java'spoll()returnsnull(andremove()throws), C++'stop()on an emptypriority_queueis undefined behaviour. - Lazy deletion bookkeeping. Counting the stale entries in
len(heap)gives wrong sizes; keep a separate live count, and make sure both heap tops are pruned after every operation that could expose a dead entry. - Off-by-one in index formulas when switching between 0-indexed (, , ) and 1-indexed (, , ) code. Pick one per file.
- Building with repeated pushes when you have all the data up front:
heapifyis , pushes are (18.9 million swaps vs 1.05 million in the measurement above). - Huge heaps from lazy Dijkstra on dense graphs. The heap can reach entries; on a complete graph with vertices that is up to tuples. Use the array version of Dijkstra for dense graphs.
Variations
- Max-heap / min-max heap. A min-max heap (Atkinson et al., 1986) alternates min and max levels, giving access to both ends and removal of either — a double-ended priority queue. Two heaps with cross-links, or a balanced BST, are the common alternatives.
- Indexed priority queue (above): a binary heap plus a position map, for decrease-key and delete-by-id.
- Bounded heap / top-K heap: capacity , evict the worst on overflow; the core of streaming top-K.
- Two heaps: median and any "split the data at a quantile" problem (generalises to the p-th percentile by keeping the size ratio at ).
- d-ary heaps, binomial, Fibonacci, pairing heaps (above).
- Leftist and skew heaps: meldable heaps built from binary trees with meld; skew heaps are the self-adjusting (amortized) version.
- Radix heaps: for monotone integer keys (Dijkstra with small integer weights), amortized per operation for maximum weight .
- Timing wheels and calendar queues (above): bucketed priority queues that trade exact ordering or generality for operations.
- Heap sort: heapify plus repeated pop, in place, worst case, not stable — Heap Sort.
- Treaps combine a BST on keys with a heap on random priorities — Treaps, Splay Trees & Skip Lists.
Practice Problems
| Problem | Pattern | Difficulty |
|---|---|---|
| Kth Largest Element in a Stream | Min-heap of size K | Easy |
| Last Stone Weight | Max-heap simulation | Easy |
| Kth Largest Element in an Array | Min-heap of size K or Quick Select | Medium |
| Top K Frequent Elements | Heap + frequency map | Medium |
| Find Median from Data Stream | Two heaps | Hard |
| Merge K Sorted Lists | Min-heap + linked list | Hard |
| Sliding Window Median | Two heaps + lazy deletion | Hard |
| Reorganize String | Max-heap + greedy | Medium |
| Task Scheduler | Max-heap + cooldown | Medium |
| Smallest Range Covering Elements from K Lists | Min-heap | Hard |
Practice ladder
Fifteen problems, easy to hard, each described in our words — open the link for the real statement.
- Last Stone Weight (LeetCode 1046) — Easy. Pure max-heap simulation: repeatedly take the two largest and push back the difference.
Hint
In Python, negate the weights; stop when at most one stone is left.
- Kth Largest Element in a Stream (LeetCode 703) — Easy. The bounded min-heap of size , maintained online.
Hint
Push each value and pop while the size exceeds ; the answer is always the root.
- Kth Largest Element in an Array (LeetCode 215) — Medium. Compare the heap () with quickselect ( expected) on the same problem.
Hint
Heap: as in problem 2. Quickselect: partition around a random pivot and recurse into one side only.
- K Closest Points to Origin (LeetCode 973) — Medium. Top-K with a computed key; a max-heap of size on distance, because you evict the farthest.
Hint
Compare squared distances; no square roots needed.
- Top K Frequent Elements (LeetCode 347) — Medium. Counting plus top-K; the bucket-sort alternative shows when a heap is not optimal.
Hint
Counter then nlargest(k, counts, key=counts.get), or buckets indexed by frequency.
- Merge k Sorted Lists (LeetCode 23) — Hard. The k-way merge on linked lists; tie-breaking when nodes are not comparable.
Hint
Push (node.val, list_index, node); the index breaks ties so nodes are never compared.
Solution
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def merge_k_lists(lists):
heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
heapq.heapify(heap)
dummy = tail = ListNode()
while heap:
_, i, node = heapq.heappop(heap)
tail.next = tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
def build(vals):
head = None
for v in reversed(vals):
head = ListNode(v, head)
return head
def to_list(node):
out = []
while node:
out.append(node.val)
node = node.next
return out
assert to_list(merge_k_lists([build([1, 4, 5]), build([1, 3, 4]), build([2, 6])])) == [1, 1, 2, 3, 4, 4, 5, 6]
assert merge_k_lists([]) is None and merge_k_lists([None]) is None
print("ok")
time for nodes in lists, extra space (the nodes are relinked, not copied).
- Kth Smallest Element in a Sorted Matrix (LeetCode 378) — Medium. Treat each row as a sorted list and k-way merge until the k-th pop; compare with binary search on the value range.
Hint
Seed the heap with the first column; after popping (v, r, c) push (matrix[r][c+1], r, c+1).
- Task Scheduler (LeetCode 621) — Medium. Max-heap of remaining counts plus a cooldown queue; then find the closed-form formula and prove it.
Hint
Simulate time: pop the most frequent available task, park it in a queue until time + n, re-insert when its cooldown ends.
Solution
import heapq
from collections import Counter, deque
def least_interval(tasks, n):
heap = [-c for c in Counter(tasks).values()]
heapq.heapify(heap)
cooling = deque() # (time it becomes available, negated remaining count)
time = 0
while heap or cooling:
time += 1
if heap:
left = heapq.heappop(heap) + 1 # run one unit of the most frequent task
if left:
cooling.append((time + n, left))
if cooling and cooling[0][0] == time:
heapq.heappush(heap, cooling.popleft()[1])
return time
def formula(tasks, n):
counts = Counter(tasks).values()
m = max(counts)
ties = sum(1 for c in counts if c == m)
return max(len(tasks), (m - 1) * (n + 1) + ties)
assert least_interval(list("AAABBB"), 2) == 8
assert least_interval(list("AAABBB"), 0) == 6
assert least_interval(list("AAAAAABCDEFG"), 2) == 16
for t, n in [("AAABBBCCDE", 3), ("ABCABCAD", 2), ("AAAA", 3)]:
assert least_interval(list(t), n) == formula(list(t), n)
print("ok")
Simulation is for total time ; the formula is . The formula comes from laying out the most frequent task with gaps of : full frames of size plus one final slot per task tied for the maximum, unless there are enough tasks to fill every gap, in which case no idle time is needed.
- Reorganize String (LeetCode 767) — Medium. Greedy with a max-heap: always place the most frequent character that is not the previous one.
Hint
Impossible exactly when some character appears more than times.
- Meeting Rooms III (LeetCode 2402) — Hard. Two heaps at once: free rooms by number and busy rooms by (end time, number); delayed meetings shift in time. (Meeting Rooms II, LeetCode 253, is the one-heap version above but is a premium problem.)
Hint
Before assigning a meeting, release every busy room whose end time is at most the meeting's start. If none is free, take the busy room that frees first and delay the meeting to its end time.
- Find Median from Data Stream (LeetCode 295) — Hard. The two-heap invariants; the follow-ups ask about bounded value ranges (use counting buckets).
Hint
Route every new value through the low heap, move its max to the high heap, then rebalance sizes.
- IPO (LeetCode 502) — Hard. Sort projects by capital requirement, push newly affordable ones into a max-heap of profit, take the best times.
Hint
A pointer over the sorted list moves only forward, so the whole thing is <span class="math" data-tex="O(n \log n)"></span>.
- Sliding Window Median (LeetCode 480) — Hard. Two heaps plus lazy deletion; the full solution, with a brute-force cross-check, is in the section above.
Hint
Keep live counts per heap and a `delayed` map; prune a heap only when a dead value reaches its top.
- Smallest Range Covering Elements from K Lists (LeetCode 632) — Hard. k-way merge while tracking the maximum; the solution is in the section above.
Hint
Only advancing the list that holds the current minimum can shrink the range.
- Shortest Routes I (CSES 1671) — Medium. Dijkstra with lazy deletion at scale ( nodes, directed edges, weights up to — distances need 64-bit integers in Java/C++).
Hint
Push `(dist, node)` on every improvement and skip popped entries whose distance is larger than the best known.
Solution
```python
import heapq
def shortest_routes(n, flights):
graph = [[] for _ in range(n + 1)]
for a, b, c in flights:
graph[a].append((b, c))
dist = [None] * (n + 1)
pq = [(0, 1)]
while pq:
d, u = heapq.heappop(pq)
if dist[u] is not None: # already settled: stale entry
continue
dist[u] = d
for v, w in graph[u]:
if dist[v] is None:
heapq.heappush(pq, (d + w, v))
return dist[1:]
assert shortest_routes(3, [(1, 2, 6), (1, 3, 2), (3, 2, 3), (1, 3, 4)]) == [0, 5, 2]
assert shortest_routes(2, [(1, 2, 10**9), (1, 2, 10**9 - 1)]) == [0, 10**9 - 1]
print("ok")
```
<span class="math" data-tex="O((n + m) \log m)"></span>. This variant settles a node the first time it is popped (a "visited" check instead of comparing with `dist`), which is equivalent for non-negative weights. On CSES, read input with `sys.stdin.buffer` — I/O dominates in Python.
Interview follow-ups
- "Why is heapify O(n) and not O(n log n)?" Sift-down cost is the node's height, and heights sum to at most (proof above). The intuition counts every node as if it were at the top.
- "Implement decrease-key." Maintain a position map updated on every swap, set the key, sift up. Or explain lazy deletion and why it has the same asymptotic bound for Dijkstra.
- "Delete an arbitrary element." With a position map: swap it with the last element, shrink, then sift the moved element up or down (it may need either). Without one: search, or lazy deletion.
- "The stream is too large to store." Top-K: bounded heap, memory. Median: exact median needs memory in a single pass; use an approximate quantile sketch (t-digest, KLL) or, for small value ranges, counting buckets.
- "What if the values are bounded integers, say 0–100?" A counting array beats a heap: insert and median.
- "Merge two heaps." Concatenate and heapify, ; if melds are frequent, use a pairing or leftist heap ( or amortized).
- "Make the priority queue thread-safe." A single lock is the honest answer; Java's
PriorityBlockingQueuedoes exactly that. Lock-free skip-list-based priority queues exist (ConcurrentSkipListMapas a priority queue) — see Lock-free programming. - "Why does Java's PriorityQueue iterator not return sorted order?" It walks the backing array, which is only heap-ordered. Pop repeatedly, or copy and sort.
- "Timers: millions of them, most cancelled." A heap with lazy cancellation grows with dead entries; a hierarchical timing wheel gives insert/cancel (Kafka, Netty, the Linux timer wheel).
- "Is a Fibonacci heap worth it for Dijkstra?" Asymptotically on dense graphs, yes; in practice almost never — pointer chasing and constants dominate, and binary or 4-ary heaps with lazy deletion win on real graphs.
- "K closest points but k is close to n." Flip it: keep the farthest, or use quickselect.
Further Reading
- Sorting & Searching — heap sort algorithm
- Graphs — Dijkstra uses a priority queue
- Linked Lists — merge K sorted lists
- Trees — heaps are complete binary trees
Course navigation. Previous: Treaps, Splay Trees & Skip Lists. Next: Tries in Depth. Module index: /algorithms/trees/. Course home: DSA: Zero to Mastery.
Related Archon pages. Heap Sort, Quickselect, Median of Medians & Order Statistics, Intervals, Complexity Analysis, CPU Scheduling, Kafka Internals, Storage Engines.
Sources.
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed., Ch. 6 (heaps, heapsort, priority queues; §6.3 for the build-heap invariant and bound) and Ch. 19 in the 3rd ed. / online chapter in the 4th (Fibonacci heaps).
- Sedgewick and Wayne, Algorithms, 4th ed., §2.4 (priority queues,
IndexMinPQ, heap construction bound). - J. W. J. Williams, "Algorithm 232: Heapsort", Communications of the ACM 7(6), 1964; R. W. Floyd, "Algorithm 245: Treesort 3", CACM 7(12), 1964.
- D. B. Johnson, "Priority queues with update and finding minimum spanning trees", Information Processing Letters 4(3), 1975 (d-ary heaps).
- J. Vuillemin, "A data structure for manipulating priority queues", CACM 21(4), 1978 (binomial queues).
- M. L. Fredman and R. E. Tarjan, "Fibonacci heaps and their uses in improved network optimization algorithms", Journal of the ACM 34(3), 596–615, 1987.
- M. L. Fredman, R. Sedgewick, D. D. Sleator, R. E. Tarjan, "The pairing heap: a new form of self-adjusting heap", Algorithmica 1, 1986; M. L. Fredman, "On the efficiency of pairing heaps and related data structures", JACM 46(4), 1999; S. Pettie, "Towards a final analysis of pairing heaps", FOCS 2005.
- D. H. Larkin, S. Sen, R. E. Tarjan, "A Back-to-Basics Empirical Study of Priority Queues", ALENEX 2014.
- G. Varghese and T. Lauck, "Hashed and Hierarchical Timing Wheels", SOSP 1987.
- R. Brown, "Calendar queues: a fast O(1) priority queue implementation for the simulation event set problem", CACM 31(10), 1988.
- Python documentation,
heapq— "Priority Queue Implementation Notes" (tie-breaking counters, lazy deletion); Java SEPriorityQueueJavadoc (linear-timeremove(Object)); Gocontainer/heap(Fix); Go runtime sourceruntime/time.go; Apache Kafka sourceserver-common/.../timer/SystemTimer.java. - cp-algorithms.com, "Dijkstra on sparse graphs" (lazy deletion with a priority queue).
Try It Yourself
Problem 1: Given the array [3, 1, 6, 5, 2, 4], build a min-heap. What does the resulting array look like?
Solution
Use bottom-up heapification starting from the last non-leaf node:
- Start: [3, 1, 6, 5, 2, 4]
- Heapify index 2 (value 6): children are 4. Swap 6 and 4 → [3, 1, 4, 5, 2, 6]
- Heapify index 1 (value 1): children are 5, 2. 1 < both, no swap.
- Heapify index 0 (value 3): children are 1, 4. Swap 3 and 1 → [1, 3, 4, 5, 2, 6]. Heapify index 1: children are 5, 2. Swap 3 and 2 → [1, 2, 4, 5, 3, 6]. Result: [1, 2, 4, 5, 3, 6]
Problem 2: Find the 3rd largest element in [7, 10, 4, 3, 20, 15] using a min-heap of size 3.
Solution
Process elements maintaining a min-heap of size 3:
- 7 → heap=[7]
- 10 → heap=[7, 10]
- 4 → heap=[4, 10, 7]
- 3 → 3 < heap[0]=4, skip (heap full, 3 is smaller than min)
- 20 → push, pop min(4) → heap=[7, 10, 20]
- 15 → push, pop min(7) → heap=[10, 20, 15] Answer: heap[0] = 10 (3rd largest)
Correction: the final heap array is [10, 15, 20], not [10, 20, 15]. After pushing 15 the array is [7, 10, 20, 15]; popping moves 15 to the root and sifts it down below 10, giving [10, 15, 20] (verified with heapq). The answer, 10, is unchanged.
Problem 3: Using the two-heap technique, find the median after inserting values [5, 15, 1, 3] one at a time.
Solution
Maintain max-heap (lower half) and min-heap (upper half):
- Insert 5: maxHeap=[-5], minHeap=[] → median = 5
- Insert 15: maxHeap=[-5], minHeap=[15] → median = (5+15)/2 = 10
- Insert 1: maxHeap=[-5, -1], minHeap=[15] → rebalance: maxHeap=[-5], push 5 to min, then rebalance → maxHeap=[-5, -1], minHeap=[15] → median = 5
- Insert 3: maxHeap=[-5, -3, -1], minHeap=[15] → rebalance → maxHeap=[-5, -3], minHeap=[5, 15] → wait, let me redo carefully. After all 4 elements [5, 15, 1, 3]: sorted = [1, 3, 5, 15], median = (3+5)/2 = 4
Correction: the worked steps above wander. Here is the trace produced by running the MedianFinder code (lower half shown as values, not negated):
| Insert | Lower half (max-heap) | Upper half (min-heap) | Median |
|---|---|---|---|
| 5 | {5} | {} | 5 |
| 15 | {5} | {15} | 10 |
| 1 | {1, 5} | {15} | 5 |
| 3 | {1, 3} | {5, 15} | 4 |
When 3 arrives it goes into the lower half, the lower half's maximum (5) moves to the upper half, and the sizes are then equal (2 and 2), so no further move is needed. Medians: 5, 10, 5, 4.
Problem 4: Merge three sorted arrays [1, 4, 7], [2, 5, 8], [3, 6, 9] using a min-heap.
Solution
Initialize heap with first element of each array: [(1,0,0), (2,1,0), (3,2,0)] (value, array_index, element_index).
- Pop 1, push 4 from array 0. Result: [1]
- Pop 2, push 5 from array 1. Result: [1, 2]
- Pop 3, push 6 from array 2. Result: [1, 2, 3]
- Pop 4, push 7 from array 0. Result: [1, 2, 3, 4]
- Continue until all elements are extracted. Result: [1, 2, 3, 4, 5, 6, 7, 8, 9]. Time: where N=9, K=3.
Problem 5: Why is building a heap from an array instead of ?
Solution
When building bottom-up, most nodes are near the bottom and need very few swaps:
- leaf nodes: 0 swaps each
- nodes at height 1: at most 1 swap each
- nodes at height 2: at most 2 swaps each
- Total work: The series converges because higher nodes (which require more work) are exponentially fewer in number.
Problem 6: In a 0-indexed binary heap of 100 elements, which indices are leaves, what is the parent of index 57, and what are the children of index 24?
Solution
Leaves are indices through 99. Parent of 57 is . Children of 24 are 49 and 50 (50 exists, so 24 has two children; index 49 is the last internal node, whose only child is 99).
Quick Quiz
1. What is the time complexity of extracting the minimum element from a min-heap?
- a)
- b)
- c)
- d)
Answer
b) — The minimum is at the root ( to access), but after removing it, the last element is moved to the root and must bubble down through at most levels to restore the heap property.
2. For finding the K-th largest element, what type and size of heap should you use?
- a) Max-heap of size
- b) Min-heap of size
- c) Max-heap of size
- d) Min-heap of size
Answer
b) Min-heap of size — Maintain a min-heap of the largest elements seen so far. When the heap exceeds size , remove the minimum. After processing all elements, the root is the -th largest.
3. In the two-heap median finding technique, what type of heap stores the lower half?
- a) Min-heap
- b) Max-heap
- c) Either works
- d) A balanced BST
Answer
b) Max-heap — The lower half uses a max-heap so the maximum of the lower half (the median candidate) is at the root in . The upper half uses a min-heap so the minimum of the upper half is also at the root.
4. Does a heap store elements in fully sorted order?
- a) Yes, always
- b) Only if it is a max-heap
- c) No -- it only guarantees the root is the min/max
- d) Only at the leaf level
Answer
c) No -- it only guarantees the root is the min/max — The heap property only ensures parent-child ordering, not sibling ordering. To get all elements in sorted order, you must extract them one by one ( total).
5. What is Python's heapq module -- a min-heap or max-heap?
- a) Max-heap
- b) Min-heap
- c) Both
- d) Neither
Answer
b) Min-heap — Python's heapq implements a min-heap only. To simulate a max-heap, negate all values before inserting and negate again when extracting.
(Python 3.14 added heappush_max, heappop_max and related functions, so "only" is now true of versions up to 3.13; the default functions are still min-heap.)
6. Lazy-deletion Dijkstra pushes a new entry on every improvement instead of calling decrease-key. What is the maximum heap size, and does the time bound change?
Answer
Up to entries (one per successful relaxation, plus the source). Each operation is because , so the total stays — the same as an indexed binary heap with decrease-key. Only memory grows.