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

<img className="block rounded-lg" src="https://mintcdn.com/devweeekends/8SzFxu49daVetHjN/images/dsa-techniques/13-heap.svg?fit=max&auto=format&n=8SzFxu49daVetHjN&q=85&s=d0f3f32a88427f97bdc0c9ed1af49b5d" alt="Heap Pattern" width="1080" height="1080" data-path="images/dsa-techniques/13-heap.svg" />

## 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!
</Note>

## Pattern Recognition Checklist

<CardGroup cols={2}>
  <Card title="Use Heap When" icon="check">
    * Need **k largest/smallest** elements
    * **Merge k sorted** lists/arrays
    * **Continuously track** min/max
    * **Priority-based** processing
    * **Median** from data stream
  </Card>

  <Card title="Don't Use When" icon="xmark">
    * Need **sorted order** (use sort)
    * Need **arbitrary access** by index
    * **Single min/max** needed once
    * Memory is very constrained
  </Card>
</CardGroup>

## When to Use

<CardGroup cols={2}>
  <Card title="Top K Elements" icon="ranking-star">
    Find k largest/smallest elements
  </Card>

  <Card title="Merge K Lists" icon="code-merge">
    Merge multiple sorted sequences
  </Card>

  <Card title="Scheduling" icon="calendar-check">
    Process by priority, deadlines
  </Card>

  <Card title="Median Finding" icon="chart-simple">
    Running median with two heaps
  </Card>
</CardGroup>

## Pattern Variations

### 1. Kth Largest Element

<CodeGroup>
  ```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();
  }
  ```
</CodeGroup>

### 2. Top K Frequent Elements

<CodeGroup>
  ```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;
  }
  ```
</CodeGroup>

### 3. Merge K Sorted Lists

<CodeGroup>
  ```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;
  }
  ```
</CodeGroup>

### 4. Find Median from Data Stream

<CodeGroup>
  ```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;
      }
  };
  ```
</CodeGroup>

### 5. K Closest Points to Origin

<CodeGroup>
  ```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;
  }
  ```
</CodeGroup>

## Classic Problems

<AccordionGroup>
  <Accordion title="1. Kth Largest Element" icon="ranking-star">
    **Pattern**: Min-heap of size k

    **Key**: Top of min-heap is kth largest after processing all
  </Accordion>

  <Accordion title="2. Merge K Sorted Lists" icon="code-merge">
    **Pattern**: Min-heap of list heads

    **Key**: Always pop smallest, push its next element
  </Accordion>

  <Accordion title="3. Find Median from Data Stream" icon="chart-simple">
    **Pattern**: Two heaps (max for small, min for large)

    **Key**: Keep heaps balanced, median from tops
  </Accordion>

  <Accordion title="4. Task Scheduler" icon="list-check">
    **Pattern**: Max-heap for most frequent tasks

    **Key**: Process most frequent first with cooldown
  </Accordion>
</AccordionGroup>

## 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
</Warning>

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

<Tabs>
  <Tab title="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  |
  </Tab>

  <Tab title="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)  |
  </Tab>
</Tabs>

## Interview Tips

<AccordionGroup>
  <Accordion title="How to Explain Your Approach" icon="comments">
    **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)."
  </Accordion>

  <Accordion title="When Interviewer Says..." icon="user-tie">
    | 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 |
  </Accordion>

  <Accordion title="Python Heap Gotchas" icon="python">
    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)`
  </Accordion>
</AccordionGroup>

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

<Steps>
  <Step title="Day 1: K Elements">
    * Solve: Kth Largest Element, Top K Frequent
    * Focus: When to use min vs max heap
  </Step>

  <Step title="Day 2: Merging">
    * Solve: Merge K Sorted Lists, K Pairs with Smallest Sum
    * Focus: Multi-source merging
  </Step>

  <Step title="Day 3: Two Heaps">
    * Solve: Find Median from Data Stream
    * Focus: Balancing two heaps
  </Step>

  <Step title="Day 4: Applications">
    * Solve: Task Scheduler, Meeting Rooms II
    * Focus: Scheduling with heaps
  </Step>
</Steps>

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