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 ⟲

Flip for Infographic

Interactive infographic on the flip side.

Click anywhere to Flip ⟲

FLIP SIDEHeap / Priority Queue

Click anywhere 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.

Top-K Elements

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

Common Problems

• Kth Largest Element in an Array
• Top K Frequent Elements
• K Closest Points to Origin
• Find K Pairs with Smallest Sums
• Kth Largest Element in a Stream

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.

Common Problems

• Merge K Sorted Lists
• Merge K Sorted Arrays
• Find K Pairs with Smallest Sums
• Smallest Range Covering Elements from K Lists
• Kth Smallest Element in a Sorted Matrix

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.

Common Problems

• Find Median from Data Stream
• Sliding Window Median
• IPO (maximize capital)
• Meeting Rooms III
• Maximum Average Subarrays

5 problems

Sliding Window Maximum

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

Common Problems

• Sliding Window Maximum
• Sliding Window Minimum
• Jump Game VI
• Constrained Subsequence Sum
• Max Value of Equation

5 problems

Task / Interval Scheduling

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

Common Problems

• Task Scheduler
• Meeting Rooms II
• Minimum Number of Arrows to Burst Balloons
• Car Pooling
• Find the Minimum Number of Rooms

5 problems

Custom Comparator / Lazy Deletion

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

Common Problems

• Find K Pairs with Smallest Sums
• Reorganize String
• Furthest Building You Can Reach
• Process Tasks Using Servers
• Maximum Performance of a Team

5 problems

Template / Approach

Template for: Top-K Elements

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_cpp

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

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}

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.

Practice Problems

Sharpen your skills with hand-picked problems.

View All Problems

Medium

Kth Largest Element in an Array

LeetCode #215

Medium

Top K Frequent Elements

LeetCode #347

Medium

K Closest Points to Origin

LeetCode #973

Easy

Kth Largest Element in a Stream

LeetCode #703

Easy

The K Weakest Rows in a Matrix

LeetCode #1337

Hard

Merge K Sorted Lists

LeetCode #23

Medium

Kth Smallest Element in a Sorted Matrix

LeetCode #378

Hard

Smallest Range Covering Elements from K Lists

LeetCode #632

Medium

Find K Pairs with Smallest Sums

LeetCode #373

Hard

Find Median from Data Stream

LeetCode #295

Hard

Sliding Window Median

LeetCode #480

Hard

IPO

LeetCode #502

Hard

Sliding Window Maximum

LeetCode #239

Medium

Jump Game VI

LeetCode #1696

Hard

Constrained Subsequence Sum

LeetCode #1425

Medium

Meeting Rooms II

LeetCode #253

Medium

Task Scheduler

LeetCode #621

Medium

Car Pooling

LeetCode #1094

Medium

Minimum Number of Arrows to Burst Balloons

LeetCode #452

Medium

Furthest Building You Can Reach

LeetCode #1642

Medium

Reorganize String

LeetCode #767

Hard

Maximum Performance of a Team

LeetCode #1383

Medium

Process Tasks Using Servers

LeetCode #1882

Heap / Priority Queue

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)

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}