Heap / Priority Queue
A heap gives you O(log n) insert and O(1) peek at the min or max. Essential for "Top K", streaming medians, scheduling, and merging sorted streams.
Time
O(n log k)
Space
O(k)
Recognize it when
- "Top K largest/smallest/frequent" elements
- Repeatedly extract the minimum or maximum
- Merge K sorted arrays or lists
- Scheduling with priorities (Task Scheduler)
Questions — ordered by difficulty
Kth Largest Element in an Array
Find the kth largest element in an unsorted array (not kth distinct).
Top K Frequent Elements
Return the k most frequent elements. Answer can be in any order. Must be better than O(n log n).
K Closest Points to Origin
Return the k closest points to the origin (0, 0). Distance is Euclidean.
Task Scheduler
Given tasks and a cooldown n, find the minimum time to execute all tasks (same task must wait n intervals between executions).
Reorganize String
Rearrange characters in a string so no two adjacent characters are the same. Return "" if impossible.
Merge k Sorted Lists
Merge k sorted linked lists into one sorted linked list.
LRU Cache
Design a data structure that follows LRU (Least Recently Used) cache eviction. Both get and put must be O(1).
Find Median from Data Stream
Design a data structure that supports adding numbers and finding the median in O(log n) and O(1) respectively.
IPO
Maximize capital after completing at most k projects. Each project has a required capital and a profit.
Smallest Range Covering Elements from K Lists
Find the smallest range [a, b] such that at least one element from each of the k sorted lists lies in the range.
LFU Cache
Design and implement a data structure for a Least Frequently Used (LFU) cache.