Heaps & Priority Queues

Jr Codex DSA Notes

Level: Intermediate–Advanced Prerequisites: Chapter 3 Time to complete: ~25 minutes

Table of Contents

1. What a Heap Guarantees
2. Array Representation
3. Heapify: Maintaining the Heap Property
4. Using Python's heapq
5. Priority Queues
6. Use Case: K Largest Elements
7. Summary & Next Steps

1. What a Heap Guarantees

A BST (Chapter 3) guarantees a global ordering (everything left is smaller, everything right is larger). A heap guarantees something weaker but cheaper to maintain: every parent is smaller (min-heap) or larger (max-heap) than its children — with no guarantee about how siblings or cousins compare to each other.

Min-Heap:                Max-Heap:
      1                        9
    /   \                    /   \
   3     2                  7     8
  / \   /                  / \   /
 5   4 6                  4   3 6

This weaker guarantee is exactly what makes heaps fast at the one thing they're built for: always knowing the minimum (or maximum) element in O(1), with O(log n) to add or remove it — you give up full sorting in exchange for a cheaper "give me the best one" operation.

2. Array Representation

Unlike a BST, a heap is conventionally stored as a plain array/list — no Node/left/right objects needed. Parent-child relationships are computed from index arithmetic:

# For a node at index i (0-indexed array):
#   left child index  = 2*i + 1
#   right child index  = 2*i + 2
#   parent index        = (i - 1) // 2

For the min-heap above, the array is [1, 3, 2, 5, 4, 6] — index 0 is the root (1), its children are at indices 1 and 2 (3 and 2), and so on. This is far more memory-efficient than a pointer-based tree (no per-node pointer overhead), which is why nearly every real heap implementation, including Python's, uses this layout.

3. Heapify: Maintaining the Heap Property

Inserting or removing an element can momentarily break the heap property; "heapifying" restores it by bubbling the offending element up or down:

def sift_up(heap, i):
    parent = (i - 1) // 2
    while i > 0 and heap[i] < heap[parent]:      # min-heap: smaller bubbles up
        heap[i], heap[parent] = heap[parent], heap[i]
        i = parent
        parent = (i - 1) // 2
    # O(log n) — at most, travels the height of the tree once
 
def sift_down(heap, i):
    n = 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
    # O(log n) — same reasoning: bounded by tree height

sift_up is used after inserting a new element at the end of the array; sift_down is used after removing the root (moving the last element to the root position and letting it settle).

4. Using Python's heapq

In practice, you rarely hand-roll heap operations — Python's standard library heapq module implements a min-heap directly on top of a regular list:

import heapq
 
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 8)
heapq.heappush(heap, 3)
# heap is now internally arranged as a valid min-heap array
 
smallest = heapq.heappop(heap)   # 1 — removes and returns the minimum
# O(log n) for both heappush and heappop
 
heapq.heapify(existing_list)      # turn an existing list into a heap in-place, O(n)
 
heapq.nsmallest(2, heap)            # [3, 5] — two smallest, without fully sorting
heapq.nlargest(2, heap)              # [8, 5] — two largest

heapq only provides a min-heap. To simulate a max-heap, negate values on the way in and out:

max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -1)
largest = -heapq.heappop(max_heap)     # negate back on the way out → 5

5. Priority Queues

A priority queue is the abstract concept — "give me the highest-priority item next" — and a heap is simply the standard way to implement it efficiently. Compare to Module 5's plain queue (FIFO, first-in-first-out): a priority queue instead always serves whichever item has the best priority, regardless of insertion order.

import heapq
 
tasks = []
heapq.heappush(tasks, (2, "write tests"))     # (priority, task) tuples
heapq.heappush(tasks, (1, "fix critical bug"))
heapq.heappush(tasks, (3, "update docs"))
 
while tasks:
    priority, task = heapq.heappop(tasks)      # always pops the lowest-priority-number first
    print(task)
# Output: fix critical bug, write tests, update docs

heapq compares tuples element-by-element, so pairing (priority, value) is the standard idiom for a priority queue in Python.

6. Use Case: K Largest Elements

Problem: Given a large list, find the k largest elements without fully sorting it.

def k_largest(items, k):
    return heapq.nlargest(k, items)
    # Internally: O(n log k) — maintains a heap of size k as it scans n items,
    # far better than fully sorting (O(n log n)) when k is small

Hand-rolled version, to see why it's O(n log k):

def k_largest_manual(items, k):
    min_heap = items[:k]
    heapq.heapify(min_heap)              # O(k)
    for item in items[k:]:
        if item > min_heap[0]:            # bigger than the current smallest-of-the-k
            heapq.heapreplace(min_heap, item)   # pop smallest, push new — O(log k)
    return min_heap
    # O(k) + O((n-k) log k) ≈ O(n log k) overall

The key idea: keep a min-heap of size k — its root is always the smallest of the current top-k candidates, so a single O(log k) comparison-and-swap per remaining element is all it takes to maintain the running top-k, instead of re-sorting everything.

7. Summary & Next Steps

Key Takeaways

• A heap guarantees parent-child ordering only (not full ordering like a BST), which is exactly what makes O(log n) insert/remove-min possible with O(1) peek-min.
• Heaps are stored as plain arrays using index arithmetic (2i+1, 2i+2, (i-1)//2) — no pointer objects needed.
• Python's heapq is a min-heap; negate values to simulate a max-heap.
• The "k largest elements via a size-k min-heap" pattern (O(n log k)) is a direct, practical payoff of understanding heaps — much better than a full O(n log n) sort when k is small.

Concept Check

1. Why does a heap only guarantee "smaller than both children," rather than a full left/right ordering like a BST?
2. Why is finding the k largest elements with a min-heap of size k faster than fully sorting the list first?
3. How would you use heapq (which only implements a min-heap) to build a max-heap?

Next Chapter

→ Chapter 5: Practice Problems

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index