8.1 Heaps & Priority Queues (Top-K & Two Heaps)

1. What Is a Heap (Priority Queue)?

A Binary Heap (also called a Priority Queue) is a complete binary tree where every parent node obeys a simple priority rule over its children:

• Min-Heap: Every parent is <= its children. That guarantees the smallest item in the entire collection is always sitting at the root (index 0)!
• Max-Heap: Every parent is >= its children. That guarantees the largest item is always sitting at the root (index 0)!

Because a Heap is always filled top-to-bottom, left-to-right with no gaps, it doesn't even need TreeNode pointers — it lives inside a plain flat array where the children of index i sit at 2*i + 1 and 2*i + 2!

2. Why Do We Need a Heap & How Does It Work?

The Pain Without a Heap

Suppose items are arriving in a stream (emergency room patients, task priorities, live stock bids) and you repeatedly need to add a new item and pull out the highest/lowest priority item:

• Unsorted Array: Adding is O(1), but finding the min/max takes O(N).
• Sorted Array: Finding the min/max is O(1), but inserting a new item shifts the array in O(N).
• Binary Heap: Peeking at the min/max is O(1), and pushing or popping only bubbles up/down the height of the tree in O(log N)!

How Sift-Up (push) and Sift-Down (pop) Work Inside the Array

1. heappush(x) — Bubble Up in O(log N): Place x at the very end of the array (bottom-right leaf). Compare x with its parent at (i - 1) // 2. While x is smaller than its parent, swap them! Since a binary tree of N nodes has height log2(N), x swaps at most log2(N) times.
2. heappop() — Bubble Down in O(log N): Save the root heap[0] to return. Move the last element of the array into heap[0], and repeatedly swap it down with its smaller child (2*i + 1 or 2*i + 2) until the Min-Heap rule holds again.
3. heapify(arr) — Build a Heap from an Unsorted Array in O(N) Time: Most candidates assume building a heap of N items takes O(N log N). In fact, calling heapq.heapify(arr) starts from the bottom-most internal nodes and sifts down, running in linear O(N) time because half the nodes are leaves that do 0 work!

Warm-Up Problem Before Top-K: Last Stone Weight

Suppose you have stones [2, 7, 4, 1, 8, 1]. Every turn, you smash the two heaviest stones y and x together:

• Put all stones into a Max-Heap.
• Pop 8 and 7 -> push 8 - 7 = 1 back into the heap (O(log N)).
• Repeat until at most 1 stone remains!

3. Basic Operations & Syntax (All 4 Languages)

import heapq

# 1. Min-Heap (default in Python heapq)
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
smallest = min_heap[0]              # peek -> 1 (O(1))
popped = heapq.heappop(min_heap)    # pop  -> 1 (O(log N))

# 2. Max-Heap in Python: Multiply values by -1 when pushing & popping!
max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -40)
largest = -max_heap[0]              # peek -> 40

4. Core Interview Patterns

Pattern A: Top-K Largest Elements (Keep a Min-Heap of Size K)

Why use a Min-Heap to find the K largest elements? Think of the heap like a VIP club with only K seats. Every time a new person arrives and the club has K + 1 people, who gets kicked out? The weakest (smallest) person in the club! A Min-Heap keeps the smallest member right at the door (heap[0]), so kicking them out takes O(log K). At the end, the K strongest (largest) members remain, and heap[0] is the K-th largest!

Pattern B: Two Heaps for Streaming Median (Find Median from Data Stream)

Maintain a Max-Heap (small) for the lower half of numbers and a Min-Heap (large) for the upper half of numbers. Keep their sizes within 1 of each other so the median is always sitting right at the top of the heaps in O(1)!

# 1. Kth Largest Element via Size-K Min-Heap:
heap = []
for x in nums:
  heapq.heappush(heap, x)
  if len(heap) > k:
      heapq.heappop(heap)  # Evict smallest of the K+1 items
return heap[0]               # Kth largest sits at root!

5. Practice On Your Own (Curated Submodule Problems)