Heaps
A heap keeps the smallest (or largest) value at the root of a complete binary tree, so that one value is always O(1) to read.
Loading visual…
Definition
A heap is a complete binary tree, meaning every level is filled left to right with no gaps, that also satisfies the heap property: in a min-heap, every parent is less than or equal to both of its children, and in a max-heap every parent is greater than or equal to both. That property only constrains parent-child pairs, not siblings or cousins, so a heap is not fully sorted, but it does guarantee that the smallest (or largest) value in the whole structure always sits at the root, where it can be read in O(1) time. Because a heap is complete, it can be stored compactly in a plain array instead of needing node objects with pointers: a node at index i has children at indexes 2i + 1 and 2i + 2, and a parent at index floor((i - 1) / 2). Adding a value means placing it in the next open array slot, the next position that keeps the tree complete, and then bubbling it up: repeatedly comparing it with its parent and swapping while it is smaller (in a min-heap) than that parent, until it either reaches the root or finds a parent it does not need to swap with. Removing the root, extract-min, means taking the root's value out, moving the very last element in the array into the root position to keep the tree complete, and then sifting it down: repeatedly swapping it with whichever of its children is smaller, until it is smaller than both children or has none. Both operations only ever travel along one path from root to leaf, so each costs O(log n), the height of a complete tree with n nodes; a priority queue, where the highest-priority item needs to come out first, is usually built directly on top of a heap for exactly this reason.
Examples
class MinHeap {
#a = [];
insert(v) {
this.#a.push(v);
let i = this.#a.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.#a[parent] <= this.#a[i]) break;
[this.#a[parent], this.#a[i]] = [this.#a[i], this.#a[parent]];
i = parent;
}
}
}
const h = new MinHeap();
[5, 3, 8, 1].forEach(v => h.insert(v));Each new value is pushed to the end of the array, then swapped upward with its parent as long as it is smaller, which is bubbling up in array form.
class MinHeap {
#a = [];
extractMin() {
const min = this.#a[0];
const last = this.#a.pop();
if (this.#a.length) {
this.#a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2;
let smallest = i;
if (l < this.#a.length && this.#a[l] < this.#a[smallest]) smallest = l;
if (r < this.#a.length && this.#a[r] < this.#a[smallest]) smallest = r;
if (smallest === i) break;
[this.#a[i], this.#a[smallest]] = [this.#a[smallest], this.#a[i]];
i = smallest;
}
}
return min;
}
}The last element takes the root's place to keep the tree complete, then repeatedly swaps down with its smaller child until both children are at least as large, restoring the heap property.
// pushing tasks with a priority number, always popping the lowest one next
const tasks = new MinHeap();
tasks.insert(3); // priority 3
tasks.insert(1); // priority 1, most urgent
tasks.insert(2);
tasks.extractMin(); // 1A priority queue only needs the next-most-urgent item quickly, which is exactly the one operation, extractMin, that a heap gives for free at the root.
Common mistakes
- Assuming a heap is fully sorted; the heap property only orders each parent against its own children, not across the whole array.
- Forgetting to move the last element to the root before sifting down during extract, which breaks the complete-tree shape.
- Using the wrong comparison direction and building a max-heap when a min-heap (or vice versa) was needed.
Key takeaways
- A heap keeps the smallest (min-heap) or largest (max-heap) value at the root, readable in O(1).
- Insert bubbles a new value up; extract-min moves the last element to the root and sifts it down; both are O(log n).
- Because a heap is complete, it stores efficiently in a plain array using index math instead of node pointers.
In a min-heap, where is the largest value guaranteed to be?
Where you see this
- Priority queues for task schedulers, where the most urgent job should always run next.
- Dijkstra's shortest path and Prim's minimum spanning tree algorithms, both built on a min-heap.
- Finding the k largest or k smallest values in a stream of data without sorting everything.
- Heap sort, which repeatedly extracts the minimum (or maximum) to build a sorted array.