Heaps

No. 08 · SVG · Bubbles and stonespriority queue · min heap · max heap · heapq

Drag across the board. Click it, then use ← → to step and Space to play.

A heap is a complete binary tree (the structure property: every level full, the last one filled left to right) where every parent is smaller than its children (the order property, for a min heap). So the minimum is always at the top. Because the tree is complete, it needs no pointers: it is just a list, with the children of index i at 2i + 1 and 2i + 2. A new value bubbles up; after a pop, the replacement sinks down like a stone. Both travel one path, so both are O(log n). Python's heapq is a min heap; for a max heap, negate values going in and coming out.

FIG. 8 · The same heap drawn twice: as a tree on the board, and as the list it really is, in the channel underneath. Dotted circles are the free slots the tree will fill next, left to right. Small numbers beside each node are its list index. Red is the value being moved; the red-ringed node is the one it is compared with. Callouts: A root (the min), B last level, C levels.

Step 1 / 1
READY
Comparisons
Swaps
Heap
Result
Codeinside heapq.heapify (simplified)
def heapify(a):                    # what heapq.heapify does, O(n)
    for i in range(len(a) // 2 - 1, -1, -1):
        sift_down(a, i)            # leaves are already heaps
def sift_down(a, i):
    while 2 * i + 1 < len(a):
        c = 2 * i + 1              # left child
        if c + 1 < len(a) and a[c + 1] < a[c]:
            c += 1                 # right child is smaller
        if a[i] <= a[c]:
            break                  # parent already smaller: done
        a[i], a[c] = a[c], a[i]    # sink down
        i = c

Examples

Heap · LeetCode 215

nums = [3, 2, 1, 5, 6, 4], k = 2. Keep a min heap of the k biggest seen so far; whenever it grows past k, pop the smallest. The root is the answer: 5. Trigger: "kth largest", "top k".

O(n log k) timeO(k) spacen pushes and pops on a heap that never exceeds k + 1
Max heap · LeetCode 1046

stones = [2, 7, 4, 1, 8, 1]. Each round smash the two heaviest; if they differ, the difference goes back. A max heap (negated) hands out the heaviest every time. Answer: 1. Trigger: "always take the largest next".

O(n log n) timeO(n) spaceup to n rounds, each two pops and a push at O(log n)

Time and space

The last column fills in when a run finishes.

OperationTimeWhyLast run on the bench
Peek (heap[0])O(1)The minimum is always at index 0.—
heappushO(log n)Append, then bubble up one path: at most one swap per level, and a complete tree has about log₂ n levels.not run yet
heappopO(log n)Move the last leaf to the root, then sink it down one path.not run yet
heapifyO(n)Half the nodes are leaves and never move; a quarter sink at most one level, an eighth two… The total is under 2n swaps.not run yet
Top k / kth largest (size-k heap)O(n log k)n pushes and pops on a heap of size k. Space O(k).not run yet

Heap vs BST

A BST (page 6) orders left < node < right, so it can search for any value. A heap only promises parent < children, nothing about left vs right. That is less order, which is why it is cheaper to keep (no balancing, no pointers) and why it can only answer one question fast: what is the smallest?

Trigger words: when the problem wants a heap

Top k

  • top k
  • kth largest
  • kth smallest
  • k closest

Keep a heap of size k: a min heap for the k largest, a max heap (negated) for the k smallest.

Always the best next

  • always take the smallest next
  • always take the largest next

Repeatedly removing the min or max while new items keep arriving: a priority queue.

Template

import heapq

nums = [5, 3, 8, 1]
heapq.heapify(nums)                # list -> min heap, in place, O(n)
print(nums[0])                     # peek smallest: 1, O(1)

heapq.heappush(nums, 2)            # add, O(log n)
print(heapq.heappop(nums))         # remove smallest: 1, O(log n)
print(heapq.heappop(nums))         # next smallest: 2

# Max heap: negate in, negate out
max_heap = []
for x in [5, 3, 8]:
    heapq.heappush(max_heap, -x)
print(-heapq.heappop(max_heap))    # largest: 8

# Top k
print(heapq.nlargest(2, [5, 3, 8, 1]))   # [8, 5]

def k_largest(nums, k):            # min heap of size k
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)    # drop the smallest
    return heap                    # heap[0] is the kth largest