Heap / Priority Queue

What is Heap?

Heap is a complete binary tree that maintains the heap property: parent is always smaller (min-heap) or larger (max-heap) than children. It provides O(log n) insertion and O(1) access to min/max.

Quick Recognition: If you need k largest/smallest, merge sorted lists, or continuously find min/max, think Heap!

Pattern Recognition Checklist

Use Heap When

Need k largest/smallest elements
Merge k sorted lists/arrays
Continuously track min/max
Priority-based processing
Median from data stream

Don't Use When

Need sorted order (use sort)
Need arbitrary access by index
Single min/max needed once
Memory is very constrained

When to Use

Top K Elements

Find k largest/smallest elements

Merge K Lists

Merge multiple sorted sequences

Scheduling

Process by priority, deadlines

Median Finding

Running median with two heaps

Pattern Variations

1. Kth Largest Element

import heapq

def find_kth_largest(nums, k):
    """Find kth largest using min-heap of size k"""
    min_heap = []
    
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    
    return min_heap[0]

# Alternative: Use nlargest
def find_kth_largest_alt(nums, k):
    return heapq.nlargest(k, nums)[-1]

2. Top K Frequent Elements

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    """Find k most frequent elements"""
    count = Counter(nums)
    
    # Min-heap of (frequency, element)
    min_heap = []
    for num, freq in count.items():
        heapq.heappush(min_heap, (freq, num))
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    
    return [num for freq, num in min_heap]

3. Merge K Sorted Lists

import heapq

def merge_k_lists(lists):
    """Merge k sorted linked lists"""
    min_heap = []
    
    # Add first element from each list
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(min_heap, (lst.val, i, lst))
    
    dummy = ListNode(0)
    current = dummy
    
    while min_heap:
        val, i, node = heapq.heappop(min_heap)
        current.next = node
        current = current.next
        
        if node.next:
            heapq.heappush(min_heap, (node.next.val, i, node.next))
    
    return dummy.next

4. Find Median from Data Stream

import heapq

class MedianFinder:
    """Two heaps: max-heap for smaller half, min-heap for larger half"""
    
    def __init__(self):
        self.small = []  # Max-heap (negated values)
        self.large = []  # Min-heap
    
    def addNum(self, num):
        # Add to max-heap (small)
        heapq.heappush(self.small, -num)
        
        # Ensure max of small <= min of large
        if self.small and self.large and -self.small[0] > self.large[0]:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        
        # Balance sizes (small can have at most 1 more)
        if len(self.small) > len(self.large) + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        if len(self.large) > len(self.small):
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)
    
    def findMedian(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

5. K Closest Points to Origin

import heapq

def k_closest(points, k):
    """Find k closest points to origin"""
    # Max-heap of (-distance, point) to keep k smallest
    max_heap = []
    
    for x, y in points:
        dist = -(x * x + y * y)  # Negate for max-heap
        
        if len(max_heap) < k:
            heapq.heappush(max_heap, (dist, [x, y]))
        elif dist > max_heap[0][0]:
            heapq.heapreplace(max_heap, (dist, [x, y]))
    
    return [point for _, point in max_heap]

Classic Problems

1. Kth Largest Element

Pattern: Min-heap of size kKey: Top of min-heap is kth largest after processing all

2. Merge K Sorted Lists

Pattern: Min-heap of list headsKey: Always pop smallest, push its next element

3. Find Median from Data Stream

Pattern: Two heaps (max for small, min for large)Key: Keep heaps balanced, median from tops

4. Task Scheduler

Pattern: Max-heap for most frequent tasksKey: Process most frequent first with cooldown

Common Mistakes

Avoid These Pitfalls:

Wrong heap type: Min-heap for k largest, max-heap for k smallest
Python max-heap: Use negative values with heapq
Heap size management: Pop when size exceeds k
Custom comparators: Be careful with lambda syntax in each language

The Counter-Intuitive Heap Choice

This confuses many beginners:

Problem	Use This Heap	Why
K largest elements	Min-heap of size k	Top is smallest of k largest
K smallest elements	Max-heap of size k	Top is largest of k smallest
Stream median	Both heaps	Max for lower half, min for upper

Complexity Quick Reference

Operation	Time	Note
Insert	O(log n)	Bubble up
Extract min/max	O(log n)	Bubble down
Peek min/max	O(1)	Root element
Build heap	O(n)	Heapify all
K largest from n	O(n log k)	Maintain size k

Interview Problems by Company

Medium
Hard

Problem	Company	Key Concept
Kth Largest Element	All FAANG	Min-heap of size k
Top K Frequent	Amazon, Google	Frequency + heap
K Closest Points	Meta, Amazon	Max-heap of size k
Sort Characters by Freq	Amazon	Frequency + max-heap
Task Scheduler	Meta	Max-heap + cooldown

Problem	Company	Key Concept
Merge K Sorted Lists	All FAANG	Min-heap of heads
Find Median Stream	Amazon, Google	Two heaps
Sliding Window Median	Google	Two heaps + removal
Smallest Range	Google	K-way merge
IPO	Amazon	Two heaps (greedy)

Interview Tips

How to Explain Your Approach

Script for interviews:

“Since I need the k largest, I’ll use a min-heap of size k.”
“I’ll iterate through all elements, pushing each to the heap.”
“When heap size exceeds k, I pop the smallest.”
“After processing all, the heap contains the k largest.”
“Time is O(n log k), space is O(k).”

When Interviewer Says...

Interviewer Says	You Should Think
”Find k largest/smallest”	Heap of size k
”Merge k sorted arrays”	Min-heap of heads
”Continuous median”	Two heaps
”Process by priority”	Priority queue
”Stream of numbers”	Heap for dynamic data

Python Heap Gotchas

Python’s heapq is a min-heap only. For max-heap:

import heapq

# Push negative values
heapq.heappush(heap, -val)

# Pop and negate
max_val = -heapq.heappop(heap)

# Peek
max_val = -heap[0]

For custom objects, use tuples: (priority, item)

Practice Problems

Problem	Difficulty	Link
Kth Largest Element	Medium	LeetCode 215
Top K Frequent Elements	Medium	LeetCode 347
Merge K Sorted Lists	Hard	LeetCode 23
Find Median from Data Stream	Hard	LeetCode 295
K Closest Points to Origin	Medium	LeetCode 973

Practice Roadmap

Day 1: K Elements

Solve: Kth Largest Element, Top K Frequent
Focus: When to use min vs max heap

Day 2: Merging

Solve: Merge K Sorted Lists, K Pairs with Smallest Sum
Focus: Multi-source merging

Day 3: Two Heaps

Solve: Find Median from Data Stream
Focus: Balancing two heaps

Day 4: Applications

Solve: Task Scheduler, Meeting Rooms II
Focus: Scheduling with heaps

Interview Tip: For “k largest/smallest” problems, think heap. Use opposite heap type to maintain window of k elements.

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

What is Heap?

Pattern Recognition Checklist

Use Heap When

Don't Use When

When to Use

Top K Elements

Merge K Lists

Scheduling

Median Finding

Pattern Variations

1. Kth Largest Element

2. Top K Frequent Elements

3. Merge K Sorted Lists

4. Find Median from Data Stream

5. K Closest Points to Origin

Classic Problems

Common Mistakes

The Counter-Intuitive Heap Choice

Complexity Quick Reference

Interview Problems by Company

Interview Tips

Practice Problems

Practice Roadmap

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

​What is Heap?

​Pattern Recognition Checklist

Use Heap When

Don't Use When

​When to Use

Top K Elements

Merge K Lists

Scheduling

Median Finding

​Pattern Variations

​1. Kth Largest Element

​2. Top K Frequent Elements

​3. Merge K Sorted Lists

​4. Find Median from Data Stream

​5. K Closest Points to Origin

​Classic Problems

​Common Mistakes

​The Counter-Intuitive Heap Choice

​Complexity Quick Reference

​Interview Problems by Company

​Interview Tips

​Practice Problems

​Practice Roadmap

What is Heap?

Pattern Recognition Checklist

When to Use

Pattern Variations

1. Kth Largest Element

2. Top K Frequent Elements

3. Merge K Sorted Lists

4. Find Median from Data Stream

5. K Closest Points to Origin

Classic Problems

Common Mistakes

The Counter-Intuitive Heap Choice

Complexity Quick Reference

Interview Problems by Company

Interview Tips

Practice Problems

Practice Roadmap