Heap Toolkit

This article covers the intuition, workflow, dry run, C++ implementation, complexity, and interview usage for Heap Toolkit.

1. Intuition

A heap is for problems where you repeatedly need the smallest or largest element without fully sorting everything.

This one pattern covers:

• heapify
• kth largest or smallest
• top k frequent
• merge k sorted lists or arrays
• median from data stream

2. How It Works

1. Choose a min-heap or max-heap
2. Push candidates
3. Pop the best priority item
4. Keep heap size small if only top k matters

3. Pattern Recognition

Think heap when you see:

• top k
• kth largest
• repeatedly extract min or max
• merge many sorted streams
• online median

4. Dry Run Example

Input:

nums = [3, 2, 1, 5, 6, 4], k = 2

Step-by-step execution with min-heap of size k:

• Push 3, 2
• Push 1, pop smallest, heap stays size 2
• Push 5, pop smallest
• Continue until heap contains the two largest elements

Final Output:

2nd largest = 5

5. Code (C++)

int findKthLargest(const vector<int>& nums, int k) {
  priority_queue<int, vector<int>, greater<int>> minHeap;

  for (int num : nums) {
    minHeap.push(num);
    if (static_cast<int>(minHeap.size()) > k) {
      minHeap.pop();
    }
  }

  return minHeap.top();
}

6. Complexity Analysis

• Kth Largest: O(n log k)
• Heapify: O(n)
• Space Complexity: usually O(k) or O(n) depending on usage

7. When to Use

• streaming top-k
• merge k sorted lists
• scheduling by priority
• median with two heaps

8. Common Mistakes

• using the wrong heap type
• sorting the whole array when k is small
• forgetting that median stream needs both balance and order

9. Variations / Extensions

• max-heap and min-heap pair for median from data stream
• heap of frequencies for top k frequent elements
• node heap for merge k sorted lists

10. LeetCode Practice Problems

Easy

• https://magicsheet.dev/questions/last-stone-weight/

Medium

• https://magicsheet.dev/questions/kth-largest-element-in-an-array/
• https://magicsheet.dev/questions/top-k-frequent-elements/
• https://magicsheet.dev/questions/merge-k-sorted-lists/

Hard

• https://magicsheet.dev/questions/find-median-from-data-stream/

11. Key Takeaways

• Heaps are about repeated best-item access, not full ordering
• Many interview problems only need the heap to stay size k

Back: Stack, Queue, and Heap Patterns