Heaps and Priority Queues: The Underestimated Pattern That Solves 20+ Interview Problems

Heaps appear in roughly 15-20% of medium-hard interview problems. Yet most students spend 5% of their study time on them. This asymmetry is an opportunity.

Once you understand how heaps work and the 5 patterns they enable, problems that looked completely different suddenly share the same solution skeleton.

---

What is a Heap?

A heap is a complete binary tree with one property:

• Min-heap: Every parent is smaller than its children. The root holds the minimum.
• Max-heap: Every parent is larger than its children. The root holds the maximum.

What it gives you:

• Get the minimum/maximum: O(1)
• Insert a new element: O(log n)
• Remove the minimum/maximum: O(log n)

What it does NOT give you:

• Search for an arbitrary element: O(n) — heaps are not sorted arrays
• Get the 2nd minimum quickly: O(log n) — you have to pop first

In Python, heapq gives you a min-heap by default.

import heapq

# Create
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 8)

# Peek at minimum (no removal)
minimum = heap[0]   # 3

# Remove and return minimum
smallest = heapq.heappop(heap)  # 3

# Convert list to heap in-place O(n)
arr = [5, 3, 8, 1, 9]
heapq.heapify(arr)  # arr is now a valid min-heap

# Max-heap hack: negate values
heapq.heappush(heap, -value)   # push as negative
max_val = -heapq.heappop(heap) # pop and negate back

---

Pattern 1: Top K Elements

Problem: Find the K largest (or smallest) elements in an array.

Naive approach: Sort the array, take first K. Time: O(n log n).

Heap approach: O(n log k) — significantly faster when K << n.

K Largest Elements

def k_largest(nums, k):
    # Maintain a min-heap of size K
    # The heap always contains the K largest seen so far
    # The minimum of the heap = Kth largest overall
    
    heap = []
    
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)  # remove the smallest, keeping K largest
    
    return list(heap)

# Or simply:
def k_largest_simple(nums, k):
    return heapq.nlargest(k, nums)  # O(n log k)

K Smallest Elements

def k_smallest(nums, k):
    # Max-heap of size K (negate to simulate max-heap)
    heap = []
    
    for num in nums:
        heapq.heappush(heap, -num)  # push negated
        if len(heap) > k:
            heapq.heappop(heap)  # removes largest (most negative)
    
    return [-x for x in heap]

# Or simply:
heapq.nsmallest(k, nums)  # O(n log k)

---

Pattern 2: Kth Largest/Smallest

LeetCode #215: Find the Kth largest element in an array.

def kth_largest(nums, k):
    # Min-heap of size K
    # When full, top of heap = Kth largest
    heap = []
    
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    
    return heap[0]  # minimum of K largest = Kth largest

Why this works: Maintain exactly K elements. Any element that would push a smaller element out of the top K gets discarded. Whatever survives is the K largest, and the minimum among them (heap top) is the Kth largest.

---

Pattern 3: Merge K Sorted Lists/Arrays

Problem: Given K sorted lists, merge them into one sorted list.

Key insight: At any point, the next element in the merged output is the minimum of the current heads of all K lists.

import heapq

def merge_k_sorted(lists):
    result = []
    heap = []
    
    # Push the first element of each list
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
            # (value, list_index, element_index)
    
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        
        # Push the next element from the same list
        next_idx = elem_idx + 1
        if next_idx < len(lists[list_idx]):
            next_val = lists[list_idx][next_idx]
            heapq.heappush(heap, (next_val, list_idx, next_idx))
    
    return result

Time: O(N log K) where N = total elements, K = number of lists.

Merge K Sorted Linked Lists (LeetCode #23) uses the same idea with ListNode objects:

def merge_k_lists(lists):
    heap = []
    
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    
    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

---

Pattern 4: Find Median from Data Stream

LeetCode #295: Design a data structure that supports adding numbers and finding the median in O(log n) and O(1) respectively.

The insight: Use two heaps:

• Max-heap for the lower half (so you can get the largest of the lower half)
• Min-heap for the upper half (so you can get the smallest of the upper half)

Keep them balanced (sizes differ by at most 1). The median is the top of one or average of both tops.

import heapq

class MedianFinder:
    def __init__(self):
        self.lower = []  # max-heap (negate values)
        self.upper = []  # min-heap
    
    def add_num(self, num):
        # Push to lower half
        heapq.heappush(self.lower, -num)
        
        # Balance: lower's max must be ≤ upper's min
        if self.lower and self.upper and (-self.lower[0] > self.upper[0]):
            val = -heapq.heappop(self.lower)
            heapq.heappush(self.upper, val)
        
        # Balance sizes
        if len(self.lower) > len(self.upper) + 1:
            val = -heapq.heappop(self.lower)
            heapq.heappush(self.upper, val)
        elif len(self.upper) > len(self.lower):
            val = heapq.heappop(self.upper)
            heapq.heappush(self.lower, -val)
    
    def find_median(self):
        if len(self.lower) > len(self.upper):
            return -self.lower[0]
        return (-self.lower[0] + self.upper[0]) / 2.0

---

Pattern 5: Sliding Window Maximum

LeetCode #239: Find the maximum in each sliding window of size K.

This is the hardest heap pattern. The trick: use a deque (monotonic decreasing queue) rather than a heap for O(n) instead of O(n log n).

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # stores indices, maintains decreasing order of values
    result = []
    
    for i, num in enumerate(nums):
        # Remove elements outside the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Remove smaller elements from the back (they can never be the max)
        while dq and nums[dq[-1]] < num:
            dq.pop()
        
        dq.append(i)
        
        # Window is full
        if i >= k - 1:
            result.append(nums[dq[0]])  # front is always the maximum
    
    return result

---

Pattern 6: Task Scheduler / Frequency Problems

LeetCode #621: Schedule tasks with a cooldown period to minimize total time.

def least_interval(tasks, n):
    from collections import Counter
    import heapq
    
    freq = Counter(tasks)
    # Max-heap: process most frequent task first
    heap = [-f for f in freq.values()]
    heapq.heapify(heap)
    
    time = 0
    from collections import deque
    cooldown = deque()  # (available_time, freq)
    
    while heap or cooldown:
        time += 1
        
        if heap:
            freq_remaining = heapq.heappop(heap) + 1  # +1 because negated
            if freq_remaining:  # still has remaining count
                cooldown.append((time + n, freq_remaining))
        
        if cooldown and cooldown[0][0] == time:
            heapq.heappush(heap, cooldown.popleft()[1])
    
    return time

---

When to Reach for a Heap

Ask these questions in order:

1. Does the problem involve finding/tracking the K largest or smallest elements? → Min/max heap of size K
2. Does the problem involve merging multiple sorted sequences? → Multi-way merge with heap
3. Does the problem involve a data stream where you need running statistics? → Two-heap median finder
4. Does the problem involve intervals with priorities (like meeting rooms, task scheduling)? → Heap on end times or priorities
5. Does the problem involve Dijkstra (shortest paths in weighted graphs)? → Min-heap on distances

---

Quick Reference: heapq API

import heapq

heap = []                          # empty heap
heapq.heappush(heap, val)          # insert, O(log n)
heapq.heappop(heap)                # remove+return min, O(log n)
heap[0]                            # peek min without removing, O(1)
heapq.heapify(lst)                 # convert list to heap in-place, O(n)
heapq.nlargest(k, iterable)        # k largest, O(n log k)
heapq.nsmallest(k, iterable)       # k smallest, O(n log k)
heapq.heappushpop(heap, val)       # push then pop (efficient), O(log n)

# Push tuples for custom ordering
heapq.heappush(heap, (priority, item))  # sorts by first element

# Max-heap simulation
heapq.heappush(heap, -val)         # negate for max-heap
max_val = -heapq.heappop(heap)     # negate back on pop

---

Problems to Solve This Week

| Problem | Pattern | Difficulty | |---|---|---| | Kth Largest Element (#215) | Top-K | Medium | | Top K Frequent Elements (#347) | Top-K | Medium | | Merge K Sorted Lists (#23) | Merge K | Hard | | Find Median from Data Stream (#295) | Two heaps | Hard | | K Closest Points to Origin (#973) | Top-K | Medium | | Task Scheduler (#621) | Frequency | Medium | | Ugly Number II (#264) | Multi-source | Medium | | Kth Smallest in Sorted Matrix (#378) | Top-K variant | Medium |

Key habit: Every time you see "top K," "Kth largest/smallest," or "minimum of maximums" — your first instinct should be heap. Practice in SCS Practice by filtering for Heaps problems.