Heaps & priority queues
Data structuresHigh priority~1.5 hO(1) peek at the min/max, O(log n) insert/extract — the structure for 'top-k' and scheduling.
Definition
A binary heap is a complete binary tree — every level full except possibly the last, which fills left to right — kept in an array, where each parent sits at index i and its children at 2i + 1 and 2i + 2. It maintains the heap invariant: each parent is ≤ both children (a min-heap) or ≥ both (a max-heap). That single ordering rule is weaker than a full sort, which is exactly the point — it costs only O(log n) to restore after a change, yet always leaves the extreme element sitting at the root.
So a heap gives O(1) access to the smallest (or largest) element and O(log n) insert and extract. It is the standard implementation of a priority queue: a queue whose pop returns the highest-priority item rather than the oldest.
Operations
| Operation | Average | Worst | Note |
|---|---|---|---|
| peek (min / max) | O(1) | O(1) | The extreme element is always the root, at index 0. |
| push (insert) | O(log n) | O(log n) | Append at the end, then sift up to restore the invariant. |
| pop (extract extreme) | O(log n) | O(log n) | Swap root with the last leaf, drop it, then sift down. |
| heapify (build from array) | O(n) | O(n) | Sift down from the last internal node up — tighter than n inserts. |
| search (arbitrary value) | O(n) | O(n) | A heap orders only parent vs. child — no order between siblings. |
When to use
Reach for a heap when you repeatedly need the smallest or largest of a changing set — the cue is a prompt asking for the top-k, the kth largest/smallest, a running median, or a merge of k sorted sequences, especially when elements arrive over time so you can't sort once up front. If you only need the order once over a fixed input, a single sort is simpler and usually faster in practice. The heap earns its keep when extractions and insertions interleave.
Techniques
Top-k with a bounded heap — to keep the k largest elements, hold a min-heap of size k: push each element and, whenever the heap exceeds k, pop the smallest. The root is then the weakest of your current best, so anything smaller is rejected in O(log k). (Symmetrically, a max-heap of size k keeps the k smallest.) This is O(n log k) — cheaper than sorting when k ≪ n.
k-way merge — to merge k sorted lists, seed a min-heap with the head of each list, then repeatedly pop the global minimum and push the next element from the list it came from. Each pop is O(log k).
Two heaps (balanced halves) — to track a running median, keep a max-heap of the smaller half and a min-heap of the larger half, rebalanced so their sizes differ by at most one. The median is read off the tops in O(1), with O(log n) inserts.
Lazy deletion — heaps don't support removing an arbitrary element cheaply, so mark entries stale and skip them when they surface at the top, rather than searching the heap to delete in place.
Related structures
Heaps vs. sorting and other ordered structures
A heap is the lightweight middle ground between an unordered array and a fully sorting|sorted one: it pays O(log n) per change to keep only the extreme element findable, where a sorted array pays O(n) to keep everything in order. When you need ordered iteration or range queries — not just the extreme — a balanced BST or a sorted structure is the better fit. A heap also underpins Dijkstra's shortest paths (a priority queue of frontier nodes) and heapsort (build a heap, then pop n times for O(n log n)).
Implementation
class MinHeap {
constructor() { this.data = []; }
peek() { return this.data[0]; }
size() { return this.data.length; }
push(x) {
this.data.push(x); // append at the next open leaf
let i = this.data.length - 1;
while (i > 0) { // sift up while smaller than its parent
const parent = (i - 1) >> 1;
if (this.data[parent] <= this.data[i]) break;
[this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
i = parent;
}
}
pop() {
const top = this.data[0];
const last = this.data.pop();
if (this.data.length > 0) {
this.data[0] = last; // move the last leaf to the root
let i = 0;
const n = this.data.length;
while (true) { // sift down toward the smaller child
let smallest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && this.data[l] < this.data[smallest]) smallest = l;
if (r < n && this.data[r] < this.data[smallest]) smallest = r;
if (smallest === i) break;
[this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
i = smallest;
}
}
return top;
}
}Worked examples
Kth largest element — given an unsorted array, find the kth largest value (here k = 3). Sorting the whole array is O(n log n) and discards most of the work. Instead keep a min-heap of size k: scan the array, push each value, and whenever the heap holds more than k elements pop the smallest. The heap always retains the k largest seen so far, and its root is the smallest of those — which, once the scan ends, is exactly the kth largest.
nums = [3, 2, 1, 5, 6, 4], k = 3 — min-heap of size 3, root is the kth largest
First three elements fill the heap. Its root (the min) is 1.
5 enters; the heap overflows, so evict the smallest (1). Root is now 2.
6 is bigger than the root, so it belongs in the top 3; evict 2. Root is now 3.
4 beats the root 3, so it joins and 3 is evicted. Root is now 4.
The heap holds the three largest {4, 5, 6}; its root, 4, is the 3rd largest. Answer: 4.
function findKthLargest(nums, k) {
const heap = new MinHeap(); // keeps the k largest seen so far
for (const x of nums) {
heap.push(x);
if (heap.size() > k) heap.pop(); // drop the smallest — it's not in the top k
}
return heap.peek(); // root = smallest of the k largest = kth largest
}The heap never holds more than k elements, so each push/pop is O(log k) and the whole scan is O(n log k) time with O(k) space — strictly better than the O(n log n) full sort when k ≪ n, and it works even if the numbers arrive as a stream you can't re-read.
Things to look out for
- Using the wrong polarity: keeping the
klargest needs a min-heap (so you can cheaply drop the smallest), not a max-heap. Getting this backwards is the classic top-k bug. - Forgetting to pop after pushing on a bounded heap — the heap grows past
kand you lose the O(log k) bound (and may return the wrong element). - Assuming a heap is sorted. It orders only parent-vs-child; iterating the backing array does not yield sorted order, and siblings have no defined order.
- Reaching for a heap when a single sort suffices. If the input is fixed and you need the full order once, sorting is simpler and often faster.
- Trying to delete or update an arbitrary element in place — that's O(n) to find. Use lazy deletion (mark stale, skip at the top) instead.
Corner cases
- Empty input —
peek/popon an empty heap; guard before reading the root. klarger than (or equal to) the number of elements — the whole set qualifies; no eviction happens.- Duplicate values — heaps handle them fine, but a top-k count may need a tie-break rule (e.g. lexicographic) for a deterministic result.
- A single element, or all elements equal.
- Even vs. odd counts for a running median — the even case averages the two middle values.