Cheatsheet›Heap / Priority Queue

CORE PATTERNHigh Frequency

Heap / Priority Queue

A heap is a complete binary tree that satisfies the heap property: every parent is smaller (min-heap) or larger (max-heap) than its children. It gives O(log N) insert/delete and O(1) peek at the extreme element. Most problems use a heap to efficiently track the running minimum, maximum, or k-th largest element as data streams in.

TimeO(N log N)

SpaceO(N)

DifficultyMedium to Hard

Key Insight

Always access the extreme element in O(1) — insert and delete in O(log N).

Flip ⟲

Heapmin-heap

peek() → 1 (min root)

FLIP SIDEHeap / Priority Queue

Tap to flip back ⟲

RECOGNITION SIGNALS (WHEN TO USE THIS PATTERN)

✓Find or maintain the k-th largest / smallest element

✓Repeatedly extract the minimum or maximum from a dynamic set

✓Schedule tasks or merge streams by priority

✓Merge k sorted arrays or lists efficiently

✓Sliding window maximum or minimum

✓Two-heap split to maintain a running median

Types of Problems (Subpatterns)

Each subpattern solves a specific type of problem. Click on a card to view its template.

✓ SELECTED

Top-K Elements

Maintain a heap of size k — evict the worst element whenever the heap overflows.

Kth Largest Element in an Array
Top K Frequent Elements
K Closest Points to Origin

5 problems

K-Way Merge

Seed a min-heap with the head of each sorted list; always pop the global minimum and push its successor.

Merge K Sorted Lists
Merge K Sorted Arrays
Find K Pairs with Smallest Sums

5 problems

Running Median (Two Heaps)

Split the stream into two halves: a max-heap for the lower half and a min-heap for the upper half.

Find Median from Data Stream
Sliding Window Median
IPO (maximize capital)

5 problems

Sliding Window Maximum

Use a monotonic deque — not a heap — to answer window max/min in O(N) total.

Sliding Window Maximum
Sliding Window Minimum
Jump Game VI

5 problems

Task / Interval Scheduling

Sort by start time; use a min-heap to greedily assign or free resources.

Task Scheduler
Meeting Rooms II
Minimum Number of Arrows to Burst Balloons

5 problems

Custom Comparator / Lazy Deletion

Custom comparators let you heap on any key; lazy deletion avoids O(N) removals.

Find K Pairs with Smallest Sums
Reorganize String
Furthest Building You Can Reach

5 problems

Template / Approach

Template for: Top-K Elements

Approach

Choose Heap Type

To find the k largest: use a MIN-heap of size k. To find the k smallest: use a MAX-heap of size k.

Push Each Element

Push every element into the heap. If size exceeds k, pop the top (worst of the k candidates).

Remaining Elements = Answer

After processing all elements, the heap contains exactly the top-k. For kth largest, the root is the answer.

Template

</>Common Template

💡Top-k skeleton using a min-heap of size k. After all elements are processed, the heap holds the k largest elements and the root is the k-th largest. Flip to max-heap for k smallest.

🔑

Key Idea:A min-heap of size k is a filter: anything smaller than the current k-th largest gets evicted immediately. After N pushes and at most N pops, total cost is O(N log k) — much better than O(N log N) full sort when k << N.

1// Top-K Largest using a min-heap of size k
2// Root = k-th largest; heap contains the k largest seen so far.
3int findKthLargest(vector<int>& nums, int k)
4{
5    // min-heap: smallest of the top-k sits at the root
6    priority_queue<int, vector<int>, greater<int>> minHeap;
7 
8    for (int x : nums)
9    {
10        minHeap.push(x);
11 
12        if ((int)minHeap.size() > k)
13        {
14            minHeap.pop();   // evict the smallest — it's not in top-k
15        }
16    }
17 
18    return minHeap.top();   // k-th largest
19}

3int findKthLargest(vector<int>& nums, int k)

5 // min-heap: smallest of the top-k sits at the root

6 priority_queue<int, vector<int>, greater<int>> minHeap;

8 for (int x : nums)

9 {

10 minHeap.push(x);

12 if ((int)minHeap.size() > k)

13 {

14 minHeap.pop(); // evict the smallest — it's not in top-k

15 }

16 }

18 return minHeap.top(); // k-th largest

19}

Heap / Priority Queue

RECOGNITION SIGNALS (WHEN TO USE THIS PATTERN)

Types of Problems (Subpatterns)

Top-K Elements

K-Way Merge

Running Median (Two Heaps)

Sliding Window Maximum

Task / Interval Scheduling

Custom Comparator / Lazy Deletion

Template / Approach

Approach

Choose Heap Type

Push Each Element

Remaining Elements = Answer

Template

Practice Problems

Kth Largest Element in an Array

Top K Frequent Elements

K Closest Points to Origin

Kth Largest Element in a Stream

The K Weakest Rows in a Matrix

Merge K Sorted Lists

Kth Smallest Element in a Sorted Matrix

Smallest Range Covering Elements from K Lists

Find K Pairs with Smallest Sums

Find Median from Data Stream

Sliding Window Median

IPO

Sliding Window Maximum

Jump Game VI

Constrained Subsequence Sum

Meeting Rooms II

Task Scheduler

Car Pooling

Minimum Number of Arrows to Burst Balloons

Furthest Building You Can Reach

Reorganize String

Maximum Performance of a Team

Process Tasks Using Servers

Heap / Priority Queue

RECOGNITION SIGNALS (WHEN TO USE THIS PATTERN)

Types of Problems (Subpatterns)

Top-K Elements

K-Way Merge

Running Median (Two Heaps)

Sliding Window Maximum

Task / Interval Scheduling

Custom Comparator / Lazy Deletion

Template / Approach

Approach

Choose Heap Type

Push Each Element

Remaining Elements = Answer

Template

Practice Problems

Kth Largest Element in an Array

Top K Frequent Elements

K Closest Points to Origin

Kth Largest Element in a Stream

The K Weakest Rows in a Matrix

Merge K Sorted Lists

Kth Smallest Element in a Sorted Matrix

Smallest Range Covering Elements from K Lists

Find K Pairs with Smallest Sums

Find Median from Data Stream

Sliding Window Median

IPO

Sliding Window Maximum

Jump Game VI

Constrained Subsequence Sum

Meeting Rooms II

Task Scheduler

Car Pooling

Minimum Number of Arrows to Burst Balloons

Furthest Building You Can Reach

Reorganize String

Maximum Performance of a Team

Process Tasks Using Servers