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 NodeNode 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 heapqheapq 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)}")

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 NodeNode class — just index arithmetic on a Python listlist.

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)])

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

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

Python’s `heapqheapq`: a min-heap for free

You rarely need to hand-write sift-up/sift-down — heapqheapq 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)

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

heapqheapq 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)

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]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)

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)

Time and space complexity

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

LeetCode problem set

#	Problem	Difficulty	The twist
215	Kth Largest Element in an Array	Medium	A size- $k$ min-heap, or `nlargestnlargest`
347	Top K Frequent Elements	Medium	Count with `CounterCounter`, then heap on the counts
23	Merge k Sorted Lists	Hard	A heap of the current head of each list, always popping the smallest

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 kk and an initial list, and whose add(val)add(val) returns the kkth largest element among all values seen so far.

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

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

Editorial

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

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

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

Why not sort? Re-sorting on every addadd 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 - 1k - 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 00 if none remain.

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

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

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)$ .

heapqheapq 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 != ba != b (equal stones destroy each other, and pushing a 00 would leave a phantom stone), and handle the empty heap at the end — [2,2][2,2] must return 00.

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 nn, identical tasks must be separated by at least nn intervals. Idle intervals are allowed. Return the minimum number of intervals needed to finish all tasks.

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

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

Editorial

Picture the most frequent task laid out first: with frequency mm it forms m - 1m - 1 gaps, each needing nn other intervals, giving a skeleton of (m - 1) * (n + 1)(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["A","A","A","B","B","B"], n = 2: m = 3m = 3, two tasks tie, so (3-1) * 3 + 2 = 8(3-1) * 3 + 2 = 8. The schedule is A B _ A B _ A BA 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)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["A","C","A","B","D","B"], n = 1 gives 66 — exactly len(tasks)len(tasks), the dense case. Omitting the maxmax returns 55, which is impossible. And n = 0n = 0 also reduces to len(tasks)len(tasks).

A heap-based simulation also works and is the more obvious “priority queue” answer: repeatedly take the n + 1n + 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 maxmax.

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)$ .
heapqheapq is always a min-heap; negate values for a max-heap.
heapifyheapify 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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Heaps and Priority Queues

What you’ll learn

A heap is a tree living inside an array

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

Python’s heapqheapq: a min-heap for free

Max-heap via the negation trick

Top-k: a min-heap of size k

Time and space complexity

LeetCode problem set

Practice — real LeetCode problems

LC 703 — Kth Largest Element in a Stream · Easy

LC 1046 — Last Stone Weight · Easy

LC 621 — Task Scheduler · Medium

Recap

Was this page helpful?

Python’s `heapqheapq`: a min-heap for free