Heaps & Priority Queues

Why this module exists

When you need quick access to the minimum or maximum element, heaps are your answer. Priority queues (implemented as heaps) power Dijkstra's algorithm, task schedulers, streaming median, and "top K" problems.

This module covers:

1. Heap properties and operations
2. Using Go's container/heap and Python's heapq
3. The "top K elements" pattern
4. Merging sorted sequences

1) What is a Heap?

A heap is a complete binary tree where each parent has a specific relationship with its children:

Min-heap: Parent ≤ children (smallest at root) Max-heap: Parent ≥ children (largest at root)

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

As an array: [1, 3, 2, 7, 4] — parent at i, children at 2i+1 and 2i+2.

2) Heap Operations

The key insight: after push/pop, we "bubble up" or "bubble down" to restore the heap property.

3) Using Heaps in Go

Go's container/heap package requires implementing an interface:

import "container/heap"

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // min-heap
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// Usage:
h := &IntHeap{3, 1, 4, 1, 5}
heap.Init(h)
heap.Push(h, 2)
min := heap.Pop(h).(int)  // 1

For max-heap, flip the Less comparison: return h[i] > h[j].

4) Using Heaps in Python

Python's heapq provides min-heap operations on a list:

import heapq

nums = [3, 1, 4, 1, 5]
heapq.heapify(nums)       # O(n) in-place heapify
heapq.heappush(nums, 2)   # O(log n)
min_val = heapq.heappop(nums)  # O(log n), returns 1

# Peek without removing:
min_val = nums[0]

For max-heap, negate values:

# Max-heap trick: store negatives
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
max_val = -heapq.heappop(max_heap)  # 5

5) Pattern: Kth Largest Element

Problem: Find the kth largest element in an unsorted array.

Approach 1: Sort — O(n log n) time, O(1) space

return sorted(nums)[-k]

Approach 2: Min-heap of size k — O(n log k) time, O(k) space

import heapq

def kth_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)

    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)  # pop + push in one operation

    return heap[0]

Why min-heap for kth largest?

• Maintain the k largest elements seen
• The smallest of these k is the kth largest
• New element joins only if it's larger than current minimum

6) Pattern: Top K Frequent Elements

Problem: Given an array, return the k most frequent elements.

from collections import Counter
import heapq

def top_k_frequent(nums, k):
    counts = Counter(nums)

    # Min-heap of (frequency, element), keep size k
    heap = []
    for num, freq in counts.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)

    return [num for freq, num in heap]

Time: O(n log k) — better than O(n log n) when k << n.

7) Pattern: Merge K Sorted Lists

Problem: Merge k sorted linked lists into one sorted list.

import heapq

def merge_k_lists(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))

    dummy = ListNode(0)
    curr = dummy

    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

Why use index i? Python compares tuples element-by-element. If values are equal, it compares nodes, which fails. The index breaks ties.

Time: O(n log k) where n = total elements, k = number of lists.

8) Two Heaps: Find Median from Data Stream

For streaming median, maintain two heaps:

• Max-heap for the smaller half
• Min-heap for the larger half

class MedianFinder:
    def __init__(self):
        self.small = []  # max-heap (store negatives)
        self.large = []  # min-heap

    def addNum(self, num):
        # Add to max-heap first
        heapq.heappush(self.small, -num)

        # Balance: move largest from small to large
        heapq.heappush(self.large, -heapq.heappop(self.small))

        # Ensure small has >= elements
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

9) When to Use Heaps

Use a heap when:

• You need repeated access to min/max
• You're processing a stream and need "best so far"
• You need to merge sorted sequences
• You want top/bottom K elements

Don't use a heap when:

• You need random access
• You need to search for arbitrary elements
• You only need min/max once (just scan)

10) Common Mistakes

• Forgetting to heapify: Python's list isn't a heap until you call heapify()
• Wrong heap type: Using min-heap when you need max (or vice versa)
• Comparing non-comparable objects: In Python, push tuples with tie-breakers
• Off-by-one in top-K: Heap of size k gives kth largest, not k largest
• Modifying heap elements directly: Always use push/pop operations

11) Complexity Summary

Outcomes

After this module, you should be able to:

• Implement and use min-heaps and max-heaps
• Apply the "top K" pattern using a fixed-size heap
• Merge K sorted sequences efficiently
• Use two heaps for streaming median problems
• Choose between sorting and heap-based solutions

Practice Set

1. Kth Largest Element in an Array (Medium) — Fixed-size min-heap
2. Top K Frequent Elements (Medium) — Frequency counting + heap
3. Merge K Sorted Lists (Hard) — Heap for multi-way merge

Start with Kth Largest to understand the fixed-size heap pattern, then Top K adds frequency counting, and Merge K shows how heaps enable efficient merging.