Heaps and Priority Queues

A heap answers one question fast, over and over: “what’s the current smallest (or largest) item?” It’s the engine behind priority queues, Dijkstra’s algorithm, and every “top-k” or “k-th largest” interview question. The elegant part: a heap is a binary tree, but it never needs a single Node object — it lives entirely inside a flat array.

What you’ll learn

• The complete binary tree invariant, and the array index math behind it: $2i+1$, $2i+2$, $(i-1)//2$.
• Sift-up (on insert) and sift-down (on pop) — how the heap invariant gets restored after each change.
• Python’s heapq module — always a min-heap, plus the negation trick for a max-heap.
• The top-k pattern: maintaining a min-heap of size $k$.

A heap is a tree living inside an array

A binary min-heap keeps one invariant: every parent is $\le$ both its children. It doesn’t have to be fully sorted — only that one local rule, checked all the way down. Because the tree is always complete (filled left-to-right, level by level, with no gaps), you can store it in a plain array and compute parent/child positions with arithmetic instead of pointers:

For a node at array index $i$ (0-indexed):

$$\text{left child} = 2i + 1 \qquad \text{right child} = 2i + 2 \qquad \text{parent} = \left\lfloor \frac{i - 1}{2} \right\rfloor$$

heap_index_math.py

def left(i):
    return 2 * i + 1
 
def right(i):
    return 2 * i + 2
 
def parent(i):
    return (i - 1) // 2
 
for i in range(6):
    p = parent(i) if i > 0 else None
    print(f"index {i}: parent={p}, left={left(i)}, right={right(i)}")

No pointers, no Node class — just index arithmetic on a Python list.

Sift-up (insert) and sift-down (pop)

Inserting appends the new value at the end, then sifts it up: swap with its parent while it’s smaller, until the invariant holds. Popping removes the root, moves the last element into its place, then sifts it down: swap with the smaller child while it’s bigger than that child.

manual_min_heap.py

class MinHeap:
    def __init__(self):
        self.data = []
 
    def _parent(self, i):
        return (i - 1) // 2
 
    def _sift_up(self, i):
        while i > 0 and self.data[self._parent(i)] > self.data[i]:
            p = self._parent(i)
            self.data[i], self.data[p] = self.data[p], self.data[i]
            i = p
 
    def _sift_down(self, i):
        n = len(self.data)
        while True:
            left, right = 2 * i + 1, 2 * i + 2
            smallest = i
            if left < n and self.data[left] < self.data[smallest]:
                smallest = left
            if right < n and self.data[right] < self.data[smallest]:
                smallest = right
            if smallest == i:
                break
            self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
            i = smallest
 
    def push(self, value):
        self.data.append(value)
        self._sift_up(len(self.data) - 1)
 
    def pop(self):
        top = self.data[0]
        last = self.data.pop()
        if self.data:
            self.data[0] = last
            self._sift_down(0)
        return top
 
 
heap = MinHeap()
for x in [5, 1, 8, 3, 9, 2]:
    heap.push(x)
 
print("pop order:", [heap.pop() for _ in range(6)])

Each sift-up/sift-down walks at most the height of the tree, which for $n$ elements is $\log_2 n$ — that’s where the heap’s signature $O(\log n)$ comes from.

sketch Sift-down after popping the root p5.js Pause Restart

The last element replaces the removed root, then repeatedly swaps with its smaller child until the min-heap invariant is restored.

Python’s heapq: a min-heap for free

You rarely need to hand-write sift-up/sift-down — heapq turns a plain list into a binary min-heap using module-level functions, no wrapper class required.

heapq_priority_queue.py

import heapq
 
nums = [5, 1, 8, 3, 9, 2, 7]
 
heap = []
for x in nums:
    heapq.heappush(heap, x)   # O(log n) each
 
print("min (peek):", heap[0])                                  # O(1)
print("full pop order:", [heapq.heappop(heap) for _ in nums])  # O(log n) each
 
# heapify: turn an existing list into a heap IN PLACE, in O(n) -- not O(n log n)
data = [9, 4, 7, 1, 3]
heapq.heapify(data)
print("heapified array:", data)

Max-heap via the negation trick

heapq is always a min-heap. For a max-heap, negate values going in and out — the smallest negative is the largest original number.

max_heap_via_negation.py

import heapq
 
nums = [4, 1, 7, 3, 8]
max_heap = [-x for x in nums]
heapq.heapify(max_heap)
 
heapq.heappush(max_heap, -10)   # push -10 to represent the value 10
largest = -heapq.heappop(max_heap)
print("largest via negation:", largest)

Top-k: a min-heap of size k

The single most common heap pattern in interviews: keep a min-heap capped at size $k$. Any new value that beats the heap’s smallest replaces it — heap[0] is always the current $k$-th largest seen so far.

k_largest_two_ways.py

import heapq
 
nums = [7, 2, 9, 4, 1, 8, 5, 3]
k = 3
 
# Way 1: heapq.nlargest -- simplest, O(n log k) under the hood
top_k_builtin = heapq.nlargest(k, nums)
 
# Way 2: maintain a min-heap of size k by hand
min_heap = []
for x in nums:
    if len(min_heap) < k:
        heapq.heappush(min_heap, x)
    elif x > min_heap[0]:
        heapq.heapreplace(min_heap, x)   # pop smallest, push x -- one O(log k) step
 
top_k_manual = sorted(min_heap, reverse=True)
 
print("builtin nlargest:", top_k_builtin)
print("manual k-heap:   ", top_k_manual)

heapreplace vs heappushpop

heapq.heapreplace(heap, x) pops then pushes (always changes the heap, even if x would’ve just come right back off). heapq.heappushpop(heap, x) pushes then pops, which is faster when x might be smaller than everything already in the heap — it avoids growing the heap at all in that case.

The cue

Reach for a heap when…

• You repeatedly need the smallest or largest element, and the collection keeps changing.
• You need the top k of a stream — a size-k heap gives $O(n \log k)$ time and, crucially, $O(k)$ space, so it works when the data does not fit in memory.
• You need the k-th smallest, or a running median (two heaps).
• Something must be processed in priority order rather than arrival order: Dijkstra, task scheduling, k-way merge.

The distinction from sorting is worth stating: sorting gives you all the order for $O(n \log n)$. A heap gives you the extremes on demand for $O(\log n)$ per operation, and never pays for order you do not use. If you only need the top 10 of a million items, sorting does 100× unnecessary work.

Reach for something else when you need arbitrary lookup or search — a heap cannot answer “is x present” faster than $O(n)$ — or when you need full sorted order anyway.

Visual intuition

Both faces at once — the tree you picture, and the array that is actually there. The index arithmetic linking them is shown under each cell:

heapAppend at the end, then bubble up until the parent promise holdspush · O(log n)

as a tree

heap is empty

as an array — the real thing

size0

1def push(heap, value):2    heap.append(value)              # always a valid TREE shape3    i = len(heap) - 14    while i > 0:5        p = (i - 1) // 26        if heap[p] <= heap[i]: break    # heap property restored7        heap[i], heap[p] = heap[p], heap[i]8        i = p

setupA min-heap keeps one promise only: every parent is ≤ its children. It says nothing about siblings, and nothing about left-to-right order — which is why a heap is not sorted and cannot answer "is x present" quickly.

Play‹›1/16⟲

Appending always keeps the tree complete, which is the property that lets an array stand in for a tree at all. The sift-up then repairs the one thing appending can break.

heapPop the root, promote the LAST leaf, then sink itpop · O(log n)

as a tree

as an array — the real thing

30518293124155206

size7

1def pop(heap):2    top = heap[0]3    heap[0] = heap[-1]              # move the LAST leaf to the root4    heap.pop()5    i = 06    while True:7        small = i8        for c in (2*i + 1, 2*i + 2):9            if c < len(heap) and heap[c] < heap[small]: small = c10        if small == i: break11        heap[i], heap[small] = heap[small], heap[i]12        i = small13    return top

setupPopping the minimum is easy — it is at index 0. Restoring the heap afterwards is the work, and the trick is counter-intuitive: fill the hole with the **last** leaf, not with the smaller child.

Play‹›1/19⟲

Filling the hole with the last leaf rather than with the smaller child is counter-intuitive but necessary: promoting a child would leave a gap in the middle of the array and break the index arithmetic everything else depends on.

Time and space complexity

Operation	Complexity
heappush (insert)	$O(\log n)$
heappop (extract-min)	$O(\log n)$
heap[0] (peek min)	$O(1)$
heapify (build from a list)	$O(n)$
nlargest(k, it) / nsmallest(k, it)	$O(n \log k)$
Search for an arbitrary value	$O(n)$
Space	$O(n)$

Why heapify is O(n), not O(n log n)

Calling heappush $n$ times costs $O(n \log n)$. heapify is smarter: it sifts down starting from the last internal node upward, and most nodes are near the bottom of the tree where sift-down is cheap — the total work sums to $O(n)$, a classic (and surprising) amortized-analysis result.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

6 problems

1 easy3 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○1046Last Stone WeighteasyNeetCode 150
• ○347Top K Frequent ElementsmediumCount with `Counter`, then heap on the countsNeetCode 150Blind 75amazonmetauberbytedance
• ○621Task SchedulermediumNeetCode 150metaamazonuber
• ○215Kth Largest Element in an ArraymediumA size-$k$ min-heap, or `nlargest`NeetCode 150LeetCode Top Interview 150
• ○23Merge k Sorted ListshardA heap of the current head of each list, always popping the smallestNeetCode 150Blind 75LeetCode Top Interview 150
• ○1851Minimum Interval to Include Each QueryhardNeetCode 150

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 703 — Kth Largest Element in a Stream · Easy

Problem. Design a class that is initialised with k and an initial list, and whose add(val) returns the kth largest element among all values seen so far.

Constraints. 1 <= k <= 10^4, up to 10^4 calls, and there are always at least k elements when add returns.

Examples. With k = 3 and [4,5,8,2]: add(3) gives 4, add(5) gives 5, add(10) gives 5, add(9) gives 8, add(4) gives 8

pch.exerciseTag pch.exerciseTitle

Editorial

The insight is inverted from what people expect: to track the kth largest you keep a min-heap of size k. Everything in the heap is among the top k, and its smallest member — the root — is exactly the kth largest.

Time $O(\log k)$ per add, $O(n)$ for the constructor via heapify. Space $O(k)$.

heapify is $O(n)$ where pushing n items individually is $O(n \log n)$ — a free improvement worth taking.

Why not sort? Re-sorting on every add is $O(n \log n)$ per call. And why not a max-heap of everything? That is $O(n)$ space and you would have to pop k - 1 items to read the answer, then push them back.

Follow-ups: “kth smallest instead?” — a max-heap via negation. “kth largest in a static array (LC 215)?” — quickselect gives $O(n)$ average. “Running median?” — two heaps. “Support removal?” — heaps cannot delete arbitrary elements; use lazy deletion.

LC 1046 — Last Stone Weight · Easy

Problem. Repeatedly take the two heaviest stones and smash them: if equal both are destroyed, otherwise the heavier one is replaced by the difference. Return the weight of the last remaining stone, or 0 if none remain.

Constraints. 1 <= len(stones) <= 30, 1 <= stones[i] <= 1000.

Examples. [2,7,4,1,8,1] gives 1 · [1] gives 1 · [2,2] gives 0

pch.exerciseTag pch.exerciseTitle

Editorial

Every step needs the two current maxima, and the result re-enters the collection — which is exactly a priority queue’s job.

Time $O(n \log n)$. Space $O(n)$.

heapq is a min-heap only, so negating on push and on pop is the standard max-heap idiom. Forgetting to negate on the way out is the classic bug.

Two details: push back only when a != b (equal stones destroy each other, and pushing a 0 would leave a phantom stone), and handle the empty heap at the end — [2,2] must return 0.

Note this is genuinely a simulation, unlike LC 1049 Last Stone Weight II, which sounds similar but collapses to a subset-sum partition. Same setup, entirely different problem — worth being able to distinguish.

Follow-ups: “Minimise the final weight by choosing which stones to smash (LC 1049)?” — that is the DP one. “Return the number of smashes?” — count loop iterations. “Very large inputs?” — still $O(n \log n)$; the heap is optimal here.

LC 621 — Task Scheduler · Medium

Problem. Given task labels and a cooldown n, identical tasks must be separated by at least n intervals. Idle intervals are allowed. Return the minimum number of intervals needed to finish all tasks.

Constraints. 1 <= len(tasks) <= 10^4, uppercase letters, 0 <= n <= 100.

Examples. ["A","A","A","B","B","B"], n = 2 gives 8 · ["A","C","A","B","D","B"], n = 1 gives 6 · ["A","A","A","B","B","B"], n = 0 gives 6

pch.exerciseTag pch.exerciseTitle

Editorial

Picture the most frequent task laid out first: with frequency m it forms m - 1 gaps, each needing n other intervals, giving a skeleton of (m - 1) * (n + 1) slots. Then add one interval for each task that ties at that maximum frequency, since each fills the final row.

For ["A","A","A","B","B","B"], n = 2: m = 3, two tasks tie, so (3-1) * 3 + 2 = 8. The schedule is A B _ A B _ A B.

But if there are many distinct tasks, every gap gets filled with real work and there is no idling — then the answer is just len(tasks). Taking the maximum of the two covers both regimes.

Time $O(n)$ to count. Space $O(|\Sigma|)$.

["A","C","A","B","D","B"], n = 1 gives 6 — exactly len(tasks), the dense case. Omitting the max returns 5, which is impossible. And n = 0 also reduces to len(tasks).

A heap-based simulation also works and is the more obvious “priority queue” answer: repeatedly take the n + 1 most frequent available tasks. It is $O(n \log 26)$ and worth describing, especially if the interviewer wants the actual schedule rather than just its length — which the formula cannot give you.

Follow-ups: “Output the schedule itself?” — use the heap simulation. “Tasks with different durations?” — much harder, a scheduling problem. “Why does the formula work?” — the two-regime argument above; be ready to justify the max.

Dry run

Top k with a size-limited heap — nums = [3, 2, 1, 5, 6, 4], k = 2, using a min-heap to find the largest values.

push	heap (sorted view)	over k?	evicted	heap after
3	[3]	no	—	[3]
2	[2,3]	no	—	[2,3]
1	[1,2,3]	yes	1	[2,3]
5	[2,3,5]	yes	2	[3,5]
6	[3,5,6]	yes	3	[5,6]
4	[4,5,6]	yes	4	[5,6]

Root is 5, the 2nd largest. The counter-intuitive part is using a min-heap for a largest query, and the reason is that the root is then exactly the element to throw away when something better arrives — and exactly the answer at the end.

Python only has a min-heap. For a max-heap, push negated values and negate on the way out. For tuples, use (-priority, item). Say this out loud; it is a small Python-specific detail interviewers listen for.

heapq.heapify is O(n), not O(n log n)

Building a heap from an existing list by sifting down from the middle backwards is $O(n)$ — the standard proof is that most nodes are near the leaves and sift down a short distance. Pushing n items one at a time is $O(n \log n)$. So heapify(existing) beats a loop of heappush, and knowing why is a common follow-up.

The variant map

Need	Approach	Complexity
k largest	min-heap of size k	$O(n \log k)$ time, $O(k)$ space
k smallest	max-heap of size k (negate)	$O(n \log k)$
k-th largest	same size-k min-heap, return the root	$O(n \log k)$
Running median	two heaps, max-heap for the low half, min-heap for the high	$O(\log n)$ per insert
Merge k sorted lists	heap of one head per list	$O(N \log k)$
Scheduling by priority	heap of (priority, task)	$O(\log n)$ per operation
Build from an existing list	heapq.heapify	$O(n)$

Two heaps for a running median: keep the sizes balanced

The max-heap holds the smaller half, the min-heap the larger half. Invariants: their sizes differ by at most one, and every element of the low half is ≤ every element of the high half. The median is then a root, or the mean of both roots. Rebalancing after every insert is what maintains it — and is the step people omit.

Interview follow-ups

They ask	What they’re checking	The answer
“Why a min-heap to find the k largest?”	Whether you understand or memorised	Its root is the smallest of the k best so far — exactly the element to evict when something better arrives, and exactly the k-th largest at the end
“Why not just sort?”	Complexity judgement	Sorting is $O(n \log n)$ and $O(n)$ space. A size-k heap is $O(n \log k)$ and $O(k)$ space, which matters when $k \ll n$ or the data is a stream
“Python has no max-heap”	Language fluency	Negate the values, or push (-priority, item) tuples
“Is heapify $O(n)$ or $O(n \log n)$?”	Depth	$O(n)$ — sift down from the middle backwards. Most nodes are near the leaves and travel a short distance
“Running median of a stream”	Whether you know the two-heap trick	Max-heap for the low half, min-heap for the high half, rebalanced to differ by at most one
“Find the k-th largest in $O(n)$ average”	Breadth	Quickselect. $O(n)$ average, $O(n^2)$ worst, and it mutates the input — trade-offs worth naming

Self-check

pch.quizTag Heaps and priority queues — self-check

1. To find the k LARGEST elements, which heap do you use and why?

   A A max-heap, so the largest is on top B A min-heap of size k — its root is the smallest of the k best, making it both the eviction candidate and the final answer C Either works identically D A sorted list is required
   pch.quizShowAnswer

   B — A min-heap of size k — its root is the smallest of the k best, making it both the eviction candidate and the final answer — The inversion is the insight. A max-heap of size k would put the wrong element within reach, so you could not cheaply decide what to discard.

2. Is heapq.heapify O(n) or O(n log n)?

   A O(n log n) — it is n pushes B O(n) — sifting down from the middle backwards, since most nodes are near the leaves and travel only a short distance C O(log n) D It depends on the input order
   pch.quizShowAnswer

   B — O(n) — sifting down from the middle backwards, since most nodes are near the leaves and travel only a short distance — A common follow-up. heapify(existing_list) is asymptotically better than a loop of heappush, and the reason is the distribution of node depths.

3. Python's heapq is a min-heap only. How do you get max-heap behaviour?

   A Use heapq.heapreplace B Negate the values on push and negate again on pop, or push (-priority, item) tuples C Reverse the list first D It is not possible
   pch.quizShowAnswer

   B — Negate the values on push and negate again on pop, or push (-priority, item) tuples — A small language-specific detail that interviewers listen for, and worth saying before you are asked.

4. You need the running median of a stream. What structure?

   A One heap B Two heaps — a max-heap for the lower half and a min-heap for the upper half, sizes differing by at most one C A sorted list with bisect D A hash map of counts
   pch.quizShowAnswer

   B — Two heaps — a max-heap for the lower half and a min-heap for the upper half, sizes differing by at most one — The median is then a root, or the mean of the two roots. The step people omit is rebalancing after every insert to preserve the size invariant.

Recall card

• Use when — repeated smallest/largest, top k, k-th, running median, or priority-ordered processing.
• Versus sorting — sorting buys all the order for $O(n \log n)$; a heap buys the extremes on demand for $O(\log n)$ each and never pays for unused order.
• Costs — push and pop $O(\log n)$; peek $O(1)$; heapify $O(n)$; search $O(n)$ (a heap cannot find arbitrary elements).
• Top k — a size-k min-heap for the k largest. $O(n \log k)$ time, $O(k)$ space.
• Python — min-heap only. Negate for a max-heap. (-priority, item) tuples.
• Two heaps for a running median, rebalanced to differ by at most one.

Recap

• A binary heap is a complete tree stored in a flat array; index math ($2i+1$, $2i+2$, $(i-1)//2$) replaces pointers entirely.
• Insert sifts up, pop sifts down — both walk at most the tree height, $O(\log n)$.
• heapq is always a min-heap; negate values for a max-heap.
• heapify builds a heap from an existing list in $O(n)$, not $O(n \log n)$.
• Top-k pattern: a size-$k$ min-heap keeps the running top-$k$ in $O(n \log k)$ total.

Next: Tries — a tree specialized for prefix search over strings.