Heap

First, the naive way

Scan for the minimum every time

Keep items in a plain list. Adding is easy (append). Taking the smallest means scanning the whole list for the minimum and removing it.

If you do that n times, each scan looks at almost everything. You could keep the list sorted instead, but then each insertion has to shift items to make room. Either way something costs O(n) per operation.

python

def drain_naive(items):
    items = list(items)
    out = []
    while items:
        m = min(items)        # O(n) scan
        items.remove(m)       # O(n) shift
        out.append(m)
    return out

print(drain_naive([5, 2, 8, 1, 9]))   # [1, 2, 5, 8, 9]

Cost: O(n) per extraction, so O(n²) to take out n items. With n = 10⁵ that is about 10¹⁰ steps.

Worked by hand

The same operations on the array

Heap array [2, 5, 3, 9, 6]. Insert 1, then extract the minimum.

step	array	what happened
start	[2, 5, 3, 9, 6]	valid: 2 ≤ 5, 3 and 5 ≤ 9, 6
insert 1	[2, 5, 3, 9, 6, 1]	placed at the end, index 5
sift up	[2, 5, 1, 9, 6, 3]	parent of index 5 is index 2 (value 3): 1 < 3, swap
sift up	[1, 5, 2, 9, 6, 3]	parent of index 2 is index 0 (value 2): 1 < 2, swap; root reached
extract-min	[3, 5, 2, 9, 6]	remove 1; move last value 3 to the root
sift down	[2, 5, 3, 9, 6]	children of the root are 5 and 2; swap with the smaller (2). Index 2 has no children: stop

1
Index arithmetic
Index 5's parent is (5 − 1) // 2 = 2. Index 0's children are 1 and 2. This arithmetic replaces the pointers a tree would normally need.
2
Why the smaller child
When sifting down, swap with the *smaller* child. Then the new parent is smaller than both its children, so the heap property holds at that spot.

Implementation

A heap from scratch

Writing it once makes heapq less mysterious. The two key helpers are the sift-up inside push and the sift-down inside pop.

Plan in plain steps

pseudocode

push(v): append v; while it has a parent and v < parent: swap with parent
pop(): remember the root; move the last item to the root; while it has a smaller child: swap with the smaller child; return the old root

python

class MinHeap:
    def __init__(self):
        self.a = []

    def push(self, v):
        a = self.a
        a.append(v)
        i = len(a) - 1
        while i > 0:
            p = (i - 1) // 2
            if a[p] <= a[i]:
                break
            a[p], a[i] = a[i], a[p]
            i = p

    def pop(self):
        a = self.a
        top, last = a[0], a.pop()
        if a:
            a[0] = last
            i, n = 0, len(a)
            while True:
                l, r, s = 2 * i + 1, 2 * i + 2, i
                if l < n and a[l] < a[s]:
                    s = l
                if r < n and a[r] < a[s]:
                    s = r
                if s == i:
                    break
                a[i], a[s] = a[s], a[i]
                i = s
        return top

h = MinHeap()
for x in [2, 5, 3, 9, 6, 1]:
    h.push(x)
print(h.a)   # [1, 5, 2, 9, 6, 3]
print(h.pop())   # 1
print(h.a)   # [2, 5, 3, 9, 6]
print([h.pop() for _ in range(5)])   # [2, 3, 5, 6, 9]

Reading the code

›push appends, then sifts up: it stops as soon as the parent is not larger (a[p] <= a[i]), so it often does very little.
›pop saves the root, pops the last item, and drops it at the root. Without the if a: guard, popping the only element would crash.
›In the sift-down loop, s tracks the smallest of the node and its two children. If it is still i, the node is in place.
›Draining a heap gives the values in sorted order: this is heap sort, O(n log n).

Implementation

Python's `heapq`

Use heapq in practice. It keeps a min-heap inside an ordinary list, and every function below is O(log n) except heapify, which is O(n).

python

import heapq

h = []
for x in [5, 2, 8, 1, 9]:
    heapq.heappush(h, x)
print(h[0])   # 1
print(heapq.heappop(h))   # 1
print(heapq.heappop(h))   # 2
print(len(h))   # 3

a = [5, 2, 8, 1, 9]
heapq.heapify(a)
print(a[0])   # 1

max_heap = []
for x in [5, 2, 8]:
    heapq.heappush(max_heap, -x)
print(-heapq.heappop(max_heap))   # 8

tasks = []
heapq.heappush(tasks, (2, "write"))
heapq.heappush(tasks, (1, "plan"))
heapq.heappush(tasks, (3, "test"))
print(heapq.heappop(tasks))   # (1, 'plan')

Reading the code

›h[0] peeks at the minimum without removing it (O(1)). The rest of the list is *not* sorted, so never read h[1] expecting the second smallest.
›heapify turns an existing list into a heap in O(n), faster than pushing each element (O(n log n)).
›heapq has only a min-heap. For a max-heap, push negated values and negate again on the way out.
›Tuples compare element by element, so (priority, item) pops by priority first. Ties then compare the items, which must be comparable; add a counter as a tie-breaker if they are not.

Worked problem

The k-th largest element

The problem

Given an unsorted list and k, return the k-th largest value (the 1st largest is the maximum).

Sorting works in O(n log n), but we only need one rank.
Keep a min-heap of size k holding the k largest values seen so far.
Push each new value. If the heap grows beyond k, pop the smallest: it cannot be among the k largest.
After the scan the heap's root is the smallest of the k largest: the k-th largest.

python

import heapq

def kth_largest(a, k):
    h = []
    for x in a:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)
    return h[0]

print(kth_largest([3, 2, 1, 5, 6, 4], 2))   # 5
print(kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))   # 4

Takeaway. A *min*-heap is the right tool for the *largest* k: its root is the weakest member, the one to evict. Time O(n log k) and memory O(k), which is far better than sorting when k is small.

Worked problem

Merge k sorted lists

The problem

Merge k sorted lists into one sorted list.

The smallest overall value must be the front of one of the lists.
Put the front of each list in a min-heap, as (value, which list, position).
Pop the smallest, append it to the output, and push the next value from the *same* list, if any.
Each of the N total values is pushed and popped once, and the heap holds at most k items.

python

import heapq

def merge_k(lists):
    h = [(l[0], i, 0) for i, l in enumerate(lists) if l]
    heapq.heapify(h)
    out = []
    while h:
        v, i, j = heapq.heappop(h)
        out.append(v)
        if j + 1 < len(lists[i]):
            heapq.heappush(h, (lists[i][j + 1], i, j + 1))
    return out

print(merge_k([[1, 4, 5], [1, 3, 4], [2, 6]]))   # [1, 1, 2, 3, 4, 4, 5, 6]
print(merge_k([[], [7]]))   # [7]

Takeaway. The heap holds only k candidates (one per list), so each step costs O(log k) instead of O(k). Total O(N log k) for N values. The list index in the tuple also breaks ties safely.

Wrap-up

Remember this

A heap keeps just enough order to give the minimum (or maximum) instantly while items are added and removed.
It is a complete tree stored in an array, with each parent at most as large as its children.
Insert sifts up and extract sifts down along a single path, so both cost O(log n).
heapq is a min-heap; negate values for a max-heap and use tuples for priorities.
Use a heap of size k for top-k and k-th largest problems, and a heap of fronts for merging k sorted sources.

Cheat sheet

Heap property: parent ≤ children (min-heap); smallest at the root
Array layout: children of i: 2i+1, 2i+2 · parent: (i−1)//2
push / pop: O(log n): sift up / sift down
peek: h[0] in O(1)
heapq: min-heap only: push −x for a max-heap; heapify(a) is O(n)
Top-k largest: min-heap of size k, evict the smallest

Top traps to avoid

Treating the heap list as sorted.
Expecting heapq to be a max-heap.
Sorting the whole list when you only need the top k.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.In a min-heap stored in an array, where is the smallest element?
2.In an array heap, what are the children of the node at index 2?
3.What is the cost of one heappush or heappop on a heap of n items?
4.“Return the k largest values from a stream of a million numbers using little memory” suggests:
5.How do you get max-heap behaviour from Python's heapq?
6.Is h[1] guaranteed to be the second-smallest item in a heap?
7.h = [5, 3, 8]; heapify; push 1; what does heappop(h) return?
8.Use a min-heap with negated numbers to get the largest of [4, 9, 2]. What is printed?
9.What does heapq.nsmallest(2, [7, 2, 9, 4, 1]) return?
10.What does list(heapq.merge([1, 4], [2, 3])) print?
11.What is the time for one heappush or heappop on a heap of n items?
12.Building a heap from n unsorted items with heapify: what is the time?
13.Why does a min-heap of negated numbers act as a max-heap?
14.Push 5, 1, 4 into an empty heap, then pop all three. What is the list of popped values?
15.Why does a heap not give a fully sorted list when you look at its array?

After this lesson you will be able to

Builds on

Unlocks

A hospital waiting room

The heap property and the array layout

Scan for the minimum every time

You only need the winner, not a full ordering

Insert, then extract the minimum

The same operations on the array

A heap from scratch

Reading the code

Python's `heapq`

Reading the code

Why log n

Edge cases

Mistakes to avoid

How to spot a heap problem

The k-th largest element

Merge k sorted lists

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up3 problems

Core6 problems

Application4 problems

Challenge2 problems