Data structure 8 of 12
Heaps and priority queues
A heap always knows its smallest item, and hands it over in O(log n). It's the structure behind every priority queue: "serve the most urgent next", whatever order things arrived in.
A 3-minute conversation: Sam asks, Priya explains
- Sam Heaps. I've heard the word but never understood them.
- Priya A heap always knows its smallest item, and hands it over in O(log n). It's the structure behind every priority queue: serve the most urgent next, whatever order things arrived in.
- Priya An emergency room. Patients aren't seen in arrival order; the most urgent goes next. And when someone new arrives, the nurse doesn't re-sort the whole waiting room, she just works out roughly where they fit.
- Sam So a heap isn't sorted?
- Priya Not fully. A min-heap only promises that every parent is smaller than its children, so the smallest is at the top. That weaker promise is what makes it fast.
- Sam How is it stored?
- Priya As a binary tree packed into a plain list, level by level. The children of index i are at two i plus one and two i plus two; the parent is at i minus one, halved. No pointers needed.
- Sam And push and pop?
- Priya Push adds at the end and sifts up: swap with the parent while smaller. Pop takes the top, moves the last item to the top, and sifts down: swap with the smaller child while bigger. Each walks one path of a tree with log n levels.
- Sam Costs?
- Priya Peek is constant. Push and pop are logarithmic. Building a heap from a list with heapify is linear. Finding an arbitrary item is linear, because heaps only know the top.
- Priya Your turn. In a heap stored as a list, where are the children of index three?
- Priya Seven and eight: two times three plus one, and two times three plus two.
- Sam In Python?
- Priya heapq, on a plain list. It's a min-heap, so for a max-heap you push negative numbers. Java's PriorityQueue takes a comparator. JavaScript has none built in.
- Sam The players?
- Priya A min-heap by hand: push and sift up. Pop and sift down, always swapping with the smaller child. And a priority queue of patients, where the smallest priority number is seen first.
- Sam Memory hook?
- Priya The emergency room. Push sifts up, pop sifts down, the top is always smallest.
- Sam Problems?
- Priya Last stone weight, smashing the two heaviest stones each turn with a max-heap. And the k-th largest element in a stream, keeping a min-heap of only the k largest; its top is the answer.
- Sam Mistakes?
- Priya Forgetting heapq is a min-heap. Treating the list as sorted. Ties between items that can't be compared. Searching inside a heap. And pushing one at a time when heapify would do.
- Sam Next?
- Priya Lesson nine, trees. You've already met one: a heap is a tree in disguise.
1. What it is
A hospital emergency room. Patients don't go in arrival order: the most urgent case is seen next. When a new patient arrives, the nurse doesn't re-sort the whole waiting room, she just works out roughly where the newcomer fits. That rough, cheap ordering is a heap.
A min-heap keeps the smallest item at the top, always. A max-heap keeps the largest. It is not fully sorted: it only guarantees that every parent is smaller than (or equal to) its children. That weaker promise is what makes it fast.
- peek the smallest:
O(1). - push a new item or pop the smallest:
O(log n). - A priority queue is a heap of (priority, item) pairs: the item with the smallest priority number comes out first.
2. How it sits in memory
A heap is a binary tree packed into a plain list, level by level. The children of index i sit at 2i + 1 and 2i + 2; its parent is at (i − 1) // 2. No pointers needed.
Push: add at the end, then sift up: swap with the parent while smaller. Pop: take the top, move the last item to the top, then sift down: swap with the smaller child while bigger. Each walks one path of a tree of height log n.
3. Operations and what they cost
| Operation | Python heapq | Cost |
|---|---|---|
| Peek the smallest | h[0] | O(1) |
| Push | heapq.heappush(h, x) | O(log n) |
| Pop the smallest | heapq.heappop(h) | O(log n) |
| Build from a list | heapq.heapify(nums) | O(n) |
| Find or remove an arbitrary item | — | O(n): heaps only know the top |
Heap or sort?Sorting everything is
O(n log n) once. A heap is better when items keep arriving, or when you only need the top few: k pops cost O(k log n).4. In Python, TypeScript and Java
Python's heapq works on a plain list and is a min-heap. For a max-heap, push negated numbers. Java's PriorityQueue takes a comparator. JavaScript has no built-in heap; interview solutions write a small one (operation A below) or use a sorted array for tiny inputs.
import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0] # 1, peek
first = heapq.heappop(h) # 1
nums = [9, 4, 7]
heapq.heapify(nums) # turns a list into a heap, O(n)
max_h = [] # max-heap: store negatives
heapq.heappush(max_h, -5)
biggest = -max_h[0] # 5
tasks = [] # priority queue of (priority, item)
heapq.heappush(tasks, (2, "email"))
heapq.heappush(tasks, (1, "fix bug"))
heapq.heappop(tasks) # (1, 'fix bug')// No built-in heap in JavaScript: use a small class like operation A.
// For a handful of items, a sorted array is fine:
const tasks: [number, string][] = [[2, "email"], [1, "fix bug"]];
tasks.sort((a, b) => a[0] - b[0]);
const next = tasks.shift(); // [1, "fix bug"]PriorityQueue<Integer> h = new PriorityQueue<>(); // min-heap
h.offer(5); h.offer(1); h.offer(3);
int smallest = h.peek(); // 1
int first = h.poll(); // 1
PriorityQueue<Integer> maxH = new PriorityQueue<>(Comparator.reverseOrder());
maxH.offer(5);
int biggest = maxH.peek(); // 5
PriorityQueue<int[]> byPriority = new PriorityQueue<>((a, b) -> a[0] - b[0]);
byPriority.offer(new int[]{2, 100}); byPriority.offer(new int[]{1, 200});5. Core operations, step by step
A heap built by hand, so sift up and sift down stop being mysterious, then the two ways you'll use heapq.
A · A min-heap by hand: push and sift up
What it doesAppends the new item, then swaps it with its parent until the parent is smaller.
Picture itA new patient sits at the end of the waiting room, then keeps swapping with the person ahead while more urgent.
Cost
O(log n): at most one swap per level.The code. Parent of index i: (i − 1) // 2.
def heap_push(h, x):
h.append(x)
i = len(h) - 1
while i > 0:
parent = (i - 1) // 2
if h[parent] <= h[i]:
break
h[parent], h[i] = h[i], h[parent]
i = parent
return hfunction heapPush(h: number[], x: number): number[] {
h.push(x);
let i = h.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (h[parent] <= h[i]) {
break;
}
[h[parent], h[i]] = [h[i], h[parent]];
i = parent;
}
return h;
}static List<Integer> heapPush(List<Integer> h, int x) {
h.add(x);
int i = h.size() - 1;
while (i > 0) {
int parent = (i - 1) / 2;
if (h.get(parent) <= h.get(i)) {
break;
}
Collections.swap(h, parent, i);
i = parent;
}
return h;
}Line by line.
| Line | What it does | Why |
|---|---|---|
h.append(x) | The new item goes in the next free spot. | Keeps the tree complete: no gaps in the list. |
parent = (i - 1) // 2 | Who is above me? | The list layout replaces pointers. |
if h[parent] <= h[i]: break | Parent already smaller: done. | The heap rule holds again. |
h[parent], h[i] = h[i], h[parent] | Swap upwards. | One level per swap: at most log n swaps. |
Watch it run. Push 1 into the heap [2, 5, 4, 9, 7].
Watch out for:
- Sorting the list after every push. O(n log n) each time instead of O(log n).
B · Pop the smallest: sift down
What it doesTakes the top, moves the last item to the top, then swaps it with its smaller child until both children are bigger.
Picture itThe most urgent patient goes in; the last arrival is moved to the front seat, then steps back past anyone more urgent.
Cost
O(log n).The code. Children of index i: 2i + 1 and 2i + 2. Always swap with the smaller child.
def heap_pop(h):
top = h[0]
last = h.pop()
if h:
h[0] = last
i = 0
while True:
small = i
for c in (2 * i + 1, 2 * i + 2):
if c < len(h) and h[c] < h[small]:
small = c
if small == i:
break
h[i], h[small] = h[small], h[i]
i = small
return topfunction heapPop(h: number[]): number {
const top = h[0];
const last = h.pop()!;
if (h.length) {
h[0] = last;
let i = 0;
while (true) {
let small = i;
for (const c of [2 * i + 1, 2 * i + 2]) {
if (c < h.length && h[c] < h[small]) small = c;
}
if (small === i) {
break;
}
[h[i], h[small]] = [h[small], h[i]];
i = small;
}
}
return top;
}static int heapPop(List<Integer> h) {
int top = h.get(0);
int last = h.remove(h.size() - 1);
if (!h.isEmpty()) {
h.set(0, last);
int i = 0;
while (true) {
int small = i;
for (int c : new int[]{2 * i + 1, 2 * i + 2}) {
if (c < h.size() && h.get(c) < h.get(small)) small = c;
}
if (small == i) {
break;
}
Collections.swap(h, i, small);
i = small;
}
}
return top;
}Line by line.
| Line | What it does | Why |
|---|---|---|
h[0] = last | The last item fills the hole at the top. | Keeps the tree complete; now fix the order. |
for c in (2 * i + 1, 2 * i + 2) | Look at both children. | Check c < len(h): a node near the bottom may have one child or none. |
h[i], h[small] = h[small], h[i] | Swap with the smaller child. | Swapping with the bigger one would put it above a smaller sibling. |
Watch it run. Pop from [1, 5, 2, 9, 7, 4].
Watch out for:
- Swapping with the left child always. Swap with the smaller child, or the heap rule breaks.
C · A priority queue of tasks
What it doesPushes (priority, task) pairs; pops always return the smallest priority number first.
Picture itThe emergency room: whoever has the most urgent triage number is seen next, whenever they arrived.
Cost
O(log n) per push and pop.The code. Python compares tuples element by element, so the priority decides.
import heapq
def serve(arrivals):
waiting = []
order = []
for priority, name in arrivals:
heapq.heappush(waiting, (priority, name))
while waiting:
priority, name = heapq.heappop(waiting)
order.append(name)
return orderfunction serve(arrivals: [number, string][]): string[] {
const waiting: [number, string][] = [];
const order: string[] = [];
for (const a of arrivals) {
waiting.push(a);
waiting.sort((p, q) => p[0] - q[0] || p[1].localeCompare(q[1])); // small inputs: keep it sorted
}
while (waiting.length) {
const [, name] = waiting.shift()!;
order.push(name);
}
return order;
}static List<String> serve(Object[][] arrivals) {
PriorityQueue<Object[]> waiting = new PriorityQueue<>((p, q) -> (int) p[0] != (int) q[0] ? (int) p[0] - (int) q[0] : ((String) p[1]).compareTo((String) q[1]));
List<String> order = new ArrayList<>();
for (Object[] a : arrivals) {
waiting.offer(a);
}
while (!waiting.isEmpty()) {
Object[] next = waiting.poll();
order.add((String) next[1]);
}
return order;
}Line by line.
| Line | What it does | Why |
|---|---|---|
heapq.heappush(waiting, (priority, name)) | The priority goes first in the tuple. | Tuples compare their first elements first. |
heapq.heappop(waiting) | The smallest priority number comes out. | Ties fall back to comparing the names. |
Watch it run. Patients arrive: cough (3), heart (1), fracture (2), rash (3).
Watch out for:
- Ties between items that can't be compared. If two priorities are equal Python compares the items next; add a counter
(priority, n, item)when items aren't comparable.
6. How to remember it
Memory hook: "The emergency room"The most urgent is always next. Newcomers bubble up past anyone less urgent; when the top leaves, the last arrival takes the seat and sinks back to where they belong.
Picture
A waiting room shaped like a pyramid, the most urgent patient on the top chair.
Chant
"Push sifts up, pop sifts down, the top is always smallest."
Key rule
Children of i are 2i + 1 and 2i + 2; the parent is (i − 1) // 2.
7. Problems solved with it
Two easy problems where a heap keeps handing you the extreme value.
LC 1046 · Last Stone Weight
The problemSmash the two heaviest stones together each turn: equal stones vanish, otherwise the difference remains. Return the last stone's weight, or 0.
What it doesA max-heap (negated values) hands over the two heaviest each turn.
Cost
O(n log n).The code. Python's heapq is a min-heap, so store negatives.
import heapq
def last_stone_weight(stones):
h = [-s for s in stones]
heapq.heapify(h)
while len(h) > 1:
a = -heapq.heappop(h)
b = -heapq.heappop(h)
if a != b:
heapq.heappush(h, -(a - b))
return -h[0] if h else 0function lastStoneWeight(stones: number[]): number {
const h = [...stones];
while (h.length > 1) {
h.sort((p, q) => q - p); // small inputs: sort instead of a heap
const a = h.shift()!;
const b = h.shift()!;
if (a !== b) {
h.push(a - b);
}
}
return h.length ? h[0] : 0;
}static int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> h = new PriorityQueue<>(Comparator.reverseOrder());
for (int s : stones) h.offer(s);
while (h.size() > 1) {
int a = h.poll();
int b = h.poll();
if (a != b) {
h.offer(a - b);
}
}
return h.isEmpty() ? 0 : h.peek();
}Line by line.
| Line | What it does | Why |
|---|---|---|
h = [-s for s in stones] | Negate so the heaviest is the smallest. | A min-heap of negatives is a max-heap. |
a = -heapq.heappop(h) | The heaviest stone. | Negate back when reading. |
heapq.heappush(h, -(a - b)) | What's left goes back in. |
Watch it run. [2, 7, 4, 1, 8, 1].
Watch out for:
- Re-sorting the whole list each turn. O(n² log n) in total. The heap keeps each turn O(log n).
LC 703 · Kth Largest Element in a Stream
The problemNumbers arrive one by one. After each, report the k-th largest seen so far.
What it doesA min-heap holding only the k largest; its top is the answer.
Cost
O(log k) per number.The code. Push each number; if the heap grows past k, pop the smallest.
import heapq
def kth_largest_stream(k, nums):
h = []
out = []
for x in nums:
heapq.heappush(h, x)
if len(h) > k:
heapq.heappop(h)
out.append(h[0])
return outfunction kthLargestStream(k: number, nums: number[]): number[] {
const h: number[] = [];
const out: number[] = [];
for (const x of nums) {
h.push(x);
h.sort((p, q) => p - q); // small inputs: keep it sorted
if (h.length > k) {
h.shift();
}
out.push(h[0]);
}
return out;
}static List<Integer> kthLargestStream(int k, int[] nums) {
PriorityQueue<Integer> h = new PriorityQueue<>();
List<Integer> out = new ArrayList<>();
for (int x : nums) {
h.offer(x);
if (h.size() > k) {
h.poll();
}
out.add(h.peek());
}
return out;
}Line by line.
| Line | What it does | Why |
|---|---|---|
if len(h) > k: heapq.heappop(h) | Too many? Drop the smallest. | The heap keeps exactly the k largest so far. |
out.append(h[0]) | The smallest of the k largest is the k-th largest. |
Watch it run. k = 3; numbers 4, 5, 8, 2, 3, 5, 10, 9, 4.
Watch out for:
- A max-heap of everything. Works, but uses O(n) memory and O(k log n) per answer.
More practice, solved on the pattern pages
| # | Problem | Level | Where |
|---|---|---|---|
| 215 | Kth Largest Element in an Array | Medium | Solved step by step on 07 · Top 'K' Elements |
| 347 | Top K Frequent Elements | Medium | Solved step by step on 07 · Top 'K' Elements |
| 973 | K Closest Points to Origin | Medium | Solved step by step on 07 · Top 'K' Elements |
| 23 | Merge k Sorted Lists | Hard | Solved step by step on 07 · Top 'K' Elements |
| 295 | Find Median from Data Stream | Hard | Solved step by step on 07 · Top 'K' Elements |
8. Common mistakes
Forgetting heapq is a min-heapFor the largest, push negatives and negate when you pop.
Treating the list as sortedOnly
h[0] is guaranteed. h[1] is not necessarily the second smallest.Comparing items that can't be comparedEqual priorities make Python compare the next tuple element. Add a tie-breaking counter.
Searching inside a heapFinding or removing an arbitrary item is O(n). If you need that, mark items as deleted and skip them when popped ("lazy deletion").
Pushing one at a time to build a heapn pushes cost O(n log n);
heapify builds it in O(n).9. Self-check quiz
Popping the smallest item from a heap of n items costs…
Sift down walks one root-to-leaf path of a tree with log n levels.
In a heap stored as a list, where are the children of index 3?
2 × 3 + 1 = 7 and 2 × 3 + 2 = 8.
How do you get a max-heap from Python's heapq?
The smallest negative is the largest number.
What does a min-heap guarantee about its list order?
Each parent ≤ its children; the top is the minimum, the rest is only partly ordered.
10. Where it shows up next
- 07 · Top K Elements: a heap of size k for the k largest, smallest or most frequent.
- 08 · Overlapping Intervals: a heap of end times counts meeting rooms.
- 20 · Shortest Path & MST: Dijkstra's algorithm pops the closest unvisited node from a heap.
Next structure: 09 · Trees and binary trees. You've already met one: a heap is a binary tree in disguise.