Heaps & Priority Queues

What is a Heap?

• Complete binary tree
• Min-heap: parent ≤ children
• Max-heap: parent ≥ children

     1
    / \
   3   2
  / \
 7   4

Array: [1, 3, 2, 7, 4]

Operations

Python heapq (Min-Heap)

import heapq

nums = [3, 1, 4]
heapq.heapify(nums)
heapq.heappush(nums, 2)
min_val = heapq.heappop(nums)

# Max-heap: negate values
heapq.heappush(heap, -x)
max_val = -heapq.heappop(heap)

Kth Largest Pattern

Keep min-heap of size k:

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

for num in nums[k:]:
    if num > heap[0]:
        heapq.heapreplace(heap, num)

return heap[0]  # kth largest

Time: O(n log k)

Top K Frequent

counts = Counter(nums)
heap = []

for num, freq in counts.items():
    heapq.heappush(heap, (freq, num))
    if len(heap) > k:
        heapq.heappop(heap)

Merge K Sorted Lists

heap = [(lst.val, i, lst) for i, lst in enumerate(lists) if lst]
heapq.heapify(heap)

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

When to Use Heaps

• Repeated min/max access
• Streaming "best so far"
• Top/bottom K elements
• Merging sorted sequences