> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Heap / Priority Queue

> Efficiently find min/max elements with heap data structure

![Heap Pattern](https://mintcdn.com/devweeekends/8SzFxu49daVetHjN/images/dsa-techniques/13-heap.svg?fit=max\&auto=format\&n=8SzFxu49daVetHjN\&q=85\&s=d0f3f32a88427f97bdc0c9ed1af49b5d)

## 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.

> [!NOTE]
>
> **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

```python Python theme={null}
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]
```

```java Java theme={null}
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();
}
```

```cpp C++ theme={null}
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

```python Python theme={null}
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]
```

```java Java theme={null}
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;
}
```

```cpp C++ theme={null}
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

```python Python theme={null}
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
```

```java Java theme={null}
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;
}
```

```cpp C++ theme={null}
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

```python Python theme={null}
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
```

```java Java theme={null}
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;
    }
}
```

```cpp C++ theme={null}
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

```python Python theme={null}
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]
```

```java Java theme={null}
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;
}
```

```cpp C++ theme={null}
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 k
>
> **Key**: Top of min-heap is kth largest after processing all

> **2. Merge K Sorted Lists**
>
> **Pattern**: Min-heap of list heads
>
> **Key**: 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 tasks
>
> **Key**: Process most frequent first with cooldown

## Common Mistakes

> [!WARNING]
>
> **Avoid These Pitfalls:**
>
> 1. **Wrong heap type**: Min-heap for k largest, max-heap for k smallest
> 2. **Python max-heap**: Use negative values with heapq
> 3. **Heap size management**: Pop when size exceeds k
> 4. **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**

| 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 |

**Hard**

| 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:**
>
> 1. "Since I need the k largest, I'll use a min-heap of size k."
> 2. "I'll iterate through all elements, pushing each to the heap."
> 3. "When heap size exceeds k, I pop the smallest."
> 4. "After processing all, the heap contains the k largest."
> 5. "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:
>
> ```python theme={null}
> 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](https://leetcode.com/problems/kth-largest-element-in-an-array/) |
| Top K Frequent Elements | Medium | [LeetCode 347](https://leetcode.com/problems/top-k-frequent-elements/) |
| Merge K Sorted Lists | Hard | [LeetCode 23](https://leetcode.com/problems/merge-k-sorted-lists/) |
| Find Median from Data Stream | Hard | [LeetCode 295](https://leetcode.com/problems/find-median-from-data-stream/) |
| K Closest Points to Origin | Medium | [LeetCode 973](https://leetcode.com/problems/k-closest-points-to-origin/) |

## Practice Roadmap

**1. Day 1: K Elements**

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

**2. Day 2: Merging**

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

**3. Day 3: Two Heaps**

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

**4. Day 4: Applications**

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

> [!TIP]
>
> **Interview Tip**: For "k largest/smallest" problems, think heap. Use opposite heap type to maintain window of k elements.


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.