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]

public int findKthLargest(int[] nums, int k) {
    // Find kth largest using min-heap of size k
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    
    return minHeap.peek();
}

int findKthLargest(vector<int>& nums, int k) {
    // Find kth largest using min-heap of size k
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    
    return minHeap.top();
}

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]

public int[] topKFrequent(int[] nums, int k) {
    // Find k most frequent elements
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {
        count.put(num, count.getOrDefault(num, 0) + 1);
    }
    
    // Min-heap of (frequency, element)
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    
    for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
        minHeap.offer(new int[]{entry.getValue(), entry.getKey()});
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = minHeap.poll()[1];
    }
    return result;
}

vector<int> topKFrequent(vector<int>& nums, int k) {
    // Find k most frequent elements
    unordered_map<int, int> count;
    for (int num : nums) {
        count[num]++;
    }
    
    // Min-heap of (frequency, element)
    priority_queue<pair<int, int>, vector<pair<int, int>>, 
                   greater<pair<int, int>>> minHeap;
    
    for (auto& [num, freq] : count) {
        minHeap.push({freq, num});
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    
    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().second);
        minHeap.pop();
    }
    return result;
}

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

public ListNode mergeKLists(ListNode[] lists) {
    // Merge k sorted linked lists
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
        (a, b) -> a.val - b.val
    );
    
    // Add first element from each list
    for (ListNode list : lists) {
        if (list != null) {
            minHeap.offer(list);
        }
    }
    
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while (!minHeap.isEmpty()) {
        ListNode node = minHeap.poll();
        current.next = node;
        current = current.next;
        
        if (node.next != null) {
            minHeap.offer(node.next);
        }
    }
    
    return dummy.next;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    // Merge k sorted linked lists
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> minHeap(cmp);
    
    // Add first element from each list
    for (ListNode* list : lists) {
        if (list != nullptr) {
            minHeap.push(list);
        }
    }
    
    ListNode dummy(0);
    ListNode* current = &dummy;
    
    while (!minHeap.empty()) {
        ListNode* node = minHeap.top();
        minHeap.pop();
        current->next = node;
        current = current->next;
        
        if (node->next != nullptr) {
            minHeap.push(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

class MedianFinder {
    // Two heaps: max-heap for smaller half, min-heap for larger half
    private PriorityQueue<Integer> small;  // Max-heap
    private PriorityQueue<Integer> large;  // Min-heap
    
    public MedianFinder() {
        small = new PriorityQueue<>(Collections.reverseOrder());
        large = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        small.offer(num);
        
        // Ensure max of small <= min of large
        if (!small.isEmpty() && !large.isEmpty() && small.peek() > large.peek()) {
            large.offer(small.poll());
        }
        
        // Balance sizes
        if (small.size() > large.size() + 1) {
            large.offer(small.poll());
        }
        if (large.size() > small.size()) {
            small.offer(large.poll());
        }
    }
    
    public double findMedian() {
        if (small.size() > large.size()) {
            return small.peek();
        }
        return (small.peek() + large.peek()) / 2.0;
    }
}

class MedianFinder {
    // Two heaps: max-heap for smaller half, min-heap for larger half
    priority_queue<int> small;  // Max-heap
    priority_queue<int, vector<int>, greater<int>> large;  // Min-heap
    
public:
    MedianFinder() {}
    
    void addNum(int num) {
        small.push(num);
        
        // Ensure max of small <= min of large
        if (!small.empty() && !large.empty() && small.top() > large.top()) {
            large.push(small.top());
            small.pop();
        }
        
        // Balance sizes
        if (small.size() > large.size() + 1) {
            large.push(small.top());
            small.pop();
        }
        if (large.size() > small.size()) {
            small.push(large.top());
            large.pop();
        }
    }
    
    double findMedian() {
        if (small.size() > large.size()) {
            return small.top();
        }
        return (small.top() + large.top()) / 2.0;
    }
};

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]

public int[][] kClosest(int[][] points, int k) {
    // Find k closest points to origin
    // Max-heap to keep k smallest
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
        (a, b) -> (b[0]*b[0] + b[1]*b[1]) - (a[0]*a[0] + a[1]*a[1])
    );
    
    for (int[] point : points) {
        maxHeap.offer(point);
        if (maxHeap.size() > k) {
            maxHeap.poll();
        }
    }
    
    int[][] result = new int[k][2];
    for (int i = 0; i < k; i++) {
        result[i] = maxHeap.poll();
    }
    return result;
}

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    // Find k closest points to origin
    auto cmp = [](vector<int>& a, vector<int>& b) {
        return a[0]*a[0] + a[1]*a[1] < b[0]*b[0] + b[1]*b[1];
    };
    priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> maxHeap(cmp);
    
    for (auto& point : points) {
        maxHeap.push(point);
        if (maxHeap.size() > k) {
            maxHeap.pop();
        }
    }
    
    vector<vector<int>> result;
    while (!maxHeap.empty()) {
        result.push_back(maxHeap.top());
        maxHeap.pop();
    }
    return result;
}

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

​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