Chapter 7: Heaps and Priority Queues

Vol 2: Algorithm Forest Adventure · Station 7

---

Metadata Card

Attribute	Value
Difficulty	(Core)
Prerequisites	Arrays (Chapter 2), Recursion and Trees
Keywords	Binary Heap Sift Up Sift Down Floyd Heap Building Heap Sort Top K d-Heap

---

Your Progress

You don't need to handle everything at once — but you need to get the most urgent item the fastest. There's a magical pile of stones in the forest that always puts the heaviest (or lightest) stone on top.

---

Breakthrough · Origins

Heap Property

A complete binary tree where every parent ≤ its children (min-heap). Stored in an array:

• Left child = 2i + 1
• Right child = 2i + 2
• Parent = (i - 1) // 2

Push (Sift Up)

def heap_push(heap, val):
    heap.append(val)
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] <= heap[i]:
            break
        heap[parent], heap[i] = heap[i], heap[parent]
        i = parent

Pop (Sift Down)

def heap_pop(heap):
    if not heap:
        return None
    if len(heap) == 1:
        return heap.pop()
    min_val = heap[0]
    heap[0] = heap.pop()
    i, n = 0, len(heap)
    while True:
        smallest = i
        left, right = 2*i+1, 2*i+2
        if left < n and heap[left] < heap[smallest]:
            smallest = left
        if right < n and heap[right] < heap[smallest]:
            smallest = right
        if smallest == i:
            break
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest
    return min_val

Floyd Heap Building (O(n))

def build_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        _sift_down(arr, i, n)

Heap Sort

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        _sift_down(arr, i, n)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        _sift_down(arr, 0, i)
    return arr

Top K Problem

import heapq

def top_k(nums, k):
    heap = []
    for val in nums:
        if len(heap) < k:
            heapq.heappush(heap, val)
        elif val > heap[0]:
            heapq.heapreplace(heap, val)
    return sorted(heap, reverse=True)

Merge K Sorted Lists

def merge_k_sorted(lists):
    heap = []
    result = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    while heap:
        val, list_idx, pos = heapq.heappop(heap)
        result.append(val)
        if pos + 1 < len(lists[list_idx]):
            heapq.heappush(heap, (lists[list_idx][pos+1], list_idx, pos+1))
    return result

---

Common Pitfalls

• Heap sort is not stable — equal elements may reorder during sift-down
• Floyd's O(n) is counterintuitive — most nodes are near the bottom and barely sift
• Use min-heap for finding Top K largest — maintain a min-heap of size K, discard the smallest

---

Verification Checklist

• [ ] Can implement push (sift up) and pop (sift down)
• [ ] Can explain why Floyd building is O(n) not O(n log n)
• [ ] Can use heap to solve Top K problems
• [ ] Can implement heap sort

---

Traveler's Notes

1. Sift up = new element climbs upward (push)
2. Sift down = replacement sinks downward (pop / Floyd)
3. Floyd = bottom-to-top sift down, not top-to-bottom insert
4. Top K with min-heap — counterintuitive but elegant

---

→ Next Stop Preview

Chapter 8: Graphs — "Beyond trees — networks and connections."