Introduction to Heaps
The best on top, and nothing else
A sorted array hands you its smallest value at once, but every insert has to shift everything after it, O(n). Often you only ever need the smallest (or the largest): the next task, the closest point, the cheapest edge. A heap keeps just that promise. It's a complete binary tree in which every parent is at most its children, a min-heap, so the smallest value is at the root. Nothing else is ordered: not siblings, not levels, not the array. In exchange, adding a value and taking the smallest each cost O(log n):
Push sifts up, pop sifts down
The tree lives in an array, as Introduction to Binary Trees stored a complete tree: the children of index i are at 2i + 1 and 2i + 2, and its parent at (i − 1) / 2, rounded down. Both operations keep the tree complete first and then repair the order along one path:
- Push puts the new value in the next free place, the end of the array, then sifts it up: while its parent is bigger, swap them.
- Pop takes the root, moves the last value into the root's place, then sifts it down: while one of its children is smaller, swap it with the smaller child.
Each walks at most one path, root to leaf, so each is O(log n):
// A min-heap in a vector: the children of i are at 2i + 1 and 2i + 2, its parent at (i - 1) / 2.
struct MinHeap {
vector<int> a;
void push(int x) {
a.push_back(x);
size_t i = a.size() - 1;
while (i > 0 && a[(i - 1) / 2] > a[i]) { // sift up while the parent is bigger
swap(a[i], a[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
int pop() {
int top = a[0];
a[0] = a.back(); // the last value takes the root, then sifts down
a.pop_back();
size_t i = 0;
while (true) {
size_t l = 2 * i + 1, r = 2 * i + 2, m = i;
if (l < a.size() && a[l] < a[m]) m = l;
if (r < a.size() && a[r] < a[m]) m = r; // the smaller child, or the bigger one ends up above it
if (m == i) break;
swap(a[i], a[m]);
i = m;
}
return top;
}
};
class MinHeap:
"""A min-heap in a list: the children of i are at 2i + 1 and 2i + 2, its parent at (i - 1) // 2."""
def __init__(self):
self.a = []
def push(self, x):
a = self.a
a.append(x)
i = len(a) - 1
while i > 0 and a[(i - 1) // 2] > a[i]: # sift up while the parent is bigger
p = (i - 1) // 2
a[i], a[p] = a[p], a[i]
i = p
def pop(self):
a = self.a
top, last = a[0], a.pop()
if a:
a[0] = last # the last value takes the root, then sifts down
i = 0
while True:
l, r, m = 2 * i + 1, 2 * i + 2, i
if l < len(a) and a[l] < a[m]:
m = l
if r < len(a) and a[r] < a[m]: # the smaller child, or the bigger one ends up above it
m = r
if m == i:
break
a[i], a[m] = a[m], a[i]
i = m
return top
// A min-heap in a list: the children of i are at 2i + 1 and 2i + 2, its parent at (i - 1) / 2.
static class MinHeap {
final List<Integer> a = new ArrayList<>();
void push(int x) {
a.add(x);
int i = a.size() - 1;
while (i > 0 && a.get((i - 1) / 2) > a.get(i)) { // sift up while the parent is bigger
Collections.swap(a, i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
int pop() {
int top = a.get(0);
int last = a.remove(a.size() - 1);
if (!a.isEmpty()) {
a.set(0, last); // the last value takes the root, then sifts down
int i = 0;
while (true) {
int l = 2 * i + 1, r = 2 * i + 2, m = i;
if (l < a.size() && a.get(l) < a.get(m)) m = l;
if (r < a.size() && a.get(r) < a.get(m)) m = r; // the smaller child, or the bigger one ends up above it
if (m == i) break;
Collections.swap(a, i, m);
i = m;
}
}
return top;
}
}
// A min-heap in an array: the children of i are at 2i + 1 and 2i + 2, its parent at (i - 1) >> 1.
// less(x, y) says x goes above y: smallest on top unless you pass another.
class MinHeap {
constructor(less = (x, y) => x < y) { this.a = []; this.less = less; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0 && this.less(a[i], a[(i - 1) >> 1])) { // sift up while the parent is bigger
const p = (i - 1) >> 1;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a;
const top = a[0], last = a.pop();
if (a.length) {
a[0] = last; // the last value takes the root, then sifts down
let i = 0;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2;
let m = i;
if (l < a.length && this.less(a[l], a[m])) m = l;
if (r < a.length && this.less(a[r], a[m])) m = r; // the smaller child, or the bigger ends up above it
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
Each pushed 5, 2, 8, 1, 9, 3, printed the array [1, 2, 3, 5, 9, 8] (a heap, not sorted: 9 sits before 8), and then popped 1 2 3 5 8 9, smallest first. Step through a push:
Pushing 1 into [2, 4, 3, 7, 8, 5] — The array under the tree is the same heap. Indigo is the value being pushed; amber, the parent it just swapped with.
And a pop:
Popping [1, 2, 3, 4, 8, 5, 7] — Green is the value that will come off, then the value that settles; indigo, the one sifting down; amber, the child it swapped with.
Sifting down has to pick the smaller child. Swap with the bigger one and it ends up above the smaller, which breaks the rule at once:
Below, you do the swaps. Push each value and lift it while its parent is bigger; then pop the heap empty, sinking each new root toward its smaller child. A wrong swap is refused, and the popped values come out sorted.
Building a heap in O(n)
To heap n values you could push them one by one, O(n log n). Building it bottom-up is cheaper: put the values in an array as they are, then sift down every parent, from the last one back to the root. When a node sifts down, both its subtrees are already heaps:
def heapify(a):
"""Bottom-up: sift down every parent, from the last one to the root."""
for start in range(len(a) // 2 - 1, -1, -1):
i = start
while True:
l, r, m = 2 * i + 1, 2 * i + 2, i
if l < len(a) and a[l] < a[m]:
m = l
if r < len(a) and a[r] < a[m]:
m = r
if m == i:
break
a[i], a[m] = a[m], a[i]
i = m
On [9, 8, 7, 6, 5, 4, 3] it gave [3, 5, 4, 6, 8, 9, 7]. Why O(n): half the nodes are leaves and never move, a quarter can sink one level, an eighth two, and so on. That sum stays under 2n, while a push can climb the whole height:
Counted on decreasing values, where every push climbs to the root:
| Values | Swaps for n pushes | Swaps to build bottom-up |
|---|---|---|
| 10,000 | 113,631 | 9,992 |
| 100,000 | 1,468,946 | 99,990 |
With Python's own heapq, a million decreasing values took 418.0 ms pushed one by one and 30.2 ms with heapify.
Heaps in your language
| Language | Heap | Order by default | Other order |
|---|---|---|---|
| Python | heapq functions on a list | smallest on top | push negatives, or tuples |
| Java | PriorityQueue | smallest on top | a Comparator, such as Comparator.reverseOrder() |
| C++ | priority_queue | largest on top | greater<int> for the smallest |
| JavaScript | none built in | write one, as above | a comparison, such as (x, y) => x > y |
- Python:
heapqworks on a plain list,heap[0]is the smallest, andheapifyis O(n).heappushpoppushes then pops;heapreplacepops then pushes. - Java:
pollandofferare O(log n), butremove(x)andcontains(x)walk the whole queue, and printing or iterating aPriorityQueueshows it in heap order, not sorted. - C++:
priority_queuekeeps the largest on top unless you passgreater<int>;topandpopare separate calls. - JavaScript: there is no heap; sorting an array on every push costs O(n) or more each time. Pairs such as
[value, list]need a comparison:<on two arrays compares them as text, so[10, 0] < [9, 1]istrue.
// A max-heap by default; greater<int> turns it into a min-heap.
void libraryHeaps() {
priority_queue<int, vector<int>, greater<int>> low; // min-heap
priority_queue<int> high; // max-heap
for (int x : {5, 1, 3}) { low.push(x); high.push(x); }
cout << low.top() << " "; low.pop();
cout << low.top() << " " << high.top() << "\n";
}
import heapq
def library_heaps():
"""heapq is a min-heap on a plain list; for a max-heap, push the negatives."""
low, high = [], []
for x in (5, 1, 3):
heapq.heappush(low, x)
heapq.heappush(high, -x)
first = heapq.heappop(low)
print(first, low[0], -high[0])
// A min-heap by natural order; a comparator makes a max-heap.
static void libraryHeaps() {
PriorityQueue<Integer> low = new PriorityQueue<>();
PriorityQueue<Integer> high = new PriorityQueue<>(Comparator.reverseOrder());
for (int x : new int[]{5, 1, 3}) { low.offer(x); high.offer(x); }
int first = low.poll();
System.out.println(first + " " + low.peek() + " " + high.peek());
}
// No heap is built in: the MinHeap above, and with (x, y) => x > y it keeps the largest on top.
function libraryHeaps() {
const low = new MinHeap(), high = new MinHeap((x, y) => x > y);
for (const x of [5, 1, 3]) { low.push(x); high.push(x); }
const first = low.pop();
console.log(first, low.a[0], high.a[0]);
}
Each printed 1 3 5: the smallest of 5, 1, 3; the smallest after popping it; and the largest from the max-heap.
Heap sort, and Last Stone Weight
Heapify, then take the top n times, and the values come out in order: heap sort, O(n log n). In place, it builds a max-heap and swaps the top to the end of the array, one value at a time. It isn't stable, and in practice your language's sort is faster, but it's how the heap guarantees its bound:
def heap_sort(a):
"""In place: a max-heap, then swap the top to the end and sift down what's left."""
def sift_down(i, n):
while True:
l, r, m = 2 * i + 1, 2 * i + 2, i
if l < n and a[l] > a[m]:
m = l
if r < n and a[r] > a[m]:
m = r
if m == i:
return
a[i], a[m] = a[m], a[i]
i = m
for i in range(len(a) // 2 - 1, -1, -1):
sift_down(i, len(a))
for end in range(len(a) - 1, 0, -1):
a[0], a[end] = a[end], a[0] # the biggest goes to the end
sift_down(0, end)
It sorted [5, 2, 8, 1, 9, 3] into [1, 2, 3, 5, 8, 9].
Last Stone Weight smashes the two heaviest stones each turn, so it wants the largest on top. In Python, push the negatives:
import heapq
def last_stone_weight(stones):
heap = [-s for s in stones] # heapq is a min-heap: negatives make it a max-heap
heapq.heapify(heap)
while len(heap) > 1:
y, x = -heapq.heappop(heap), -heapq.heappop(heap) # the two heaviest
if y != x:
heapq.heappush(heap, -(y - x))
return -heap[0] if heap else 0
It returned 1 for the example [2, 7, 4, 1, 8, 1] and 1 for [1]. Each turn is two pops and at most one push, O(n log n) in all.
Spotting it, and when it breaks
The clues. "The smallest" or "the largest" asked again and again while values keep arriving or leaving; "the next" task, event or meeting; "repeatedly take the best two": a heap.
The near-misses. Values that never change: sort once (Sorting). Only one minimum, once: a single pass. The smallest or largest of a sliding window: a monotonic deque is O(1) per step (Monotonic Deque: the Window's Maximum). A floor or ceiling, not just the top: an ordered set (Balanced Trees and Ordered Sets).
When it breaks. A heap can't find or delete an arbitrary value fast: Java's remove(x) is O(n), and the usual fix is to skip stale entries when they reach the top. It knows nothing about order below the root, so it can't list its values sorted without popping them all.
Bugs that cost a submission
Sifting down toward the bigger child.
def sift_down(a, i):
while True:
l, r, m = 2 * i + 1, 2 * i + 2, i
if l < len(a) and a[l] < a[m]:
m = l
if r < len(a) and a[r] > a[m]: # picks the bigger child when both are smaller
m = r
if m == i:
return
a[i], a[m] = a[m], a[i]
i = m
Popping [1, 2, 3, 4, 8, 5, 7] until empty gave 1 3 5 7 8 2 4; the answer is 1 2 3 4 5 7 8. Compare the right child with the left one's winner, a[r] < a[m], so the smaller child rises.
A comparator that overflows (Java).
static PriorityQueue<Integer> minHeap() {
return new PriorityQueue<>((x, y) -> x - y); // x - y overflows for values far apart
}
With −2,000,000,000 and 2,000,000,000 queued it polled 2000000000 first: x - y overflowed and flipped the sign. Use Integer.compare(x, y), or no comparator at all for natural order.
The default priority_queue as a min-heap (C++).
// meant as a min-heap
priority_queue<int> pq;
After pushing 5, 1 and 3, top() was 5, the largest. Declare priority_queue<int, vector<int>, greater<int>> for the smallest on top.
Sorting on every push (JavaScript).
function sortedPushes(vals) {
const a = [];
for (const x of vals) { a.push(x); a.sort((p, q) => p - q); } // a sorted array, re-sorted on every push
return a[0];
}
For 8,000 values it took 740.8 ms against 6.5 ms for the heap above, with the same answer. Even a sort that's quick on nearly sorted input moves the whole array each time.
Check yourself
Quiz
1 / 6Multiple choice
[1, 3, 2, 7, 4, 5], which index holds the parent of index 4?Multiple choice
[1, 3, 2, 7, 4, 5]. How many swaps does it take?Multiple choice
Multiple choice
Multiple choice
Multiple choice
Practice problems
In this order:
- Priority Queue via Binary Heap: push and pop by hand.
- Min-Heap & Max-Heap Implementation: the same sift with the order flipped.
- Validate Heap Property in Array: every parent against its children.
- Convert Min Heap to Max Heap: build bottom-up, in O(n).
- Last Stone Weight: a max-heap of stones.
Next, Top K and the Kth Element: a heap of size k for the best k values.