Heap Exercises: Priority Queue Practice Problems
Time to practice. Heaps shine on “which are the k most/least extreme” and “always give me the next-best” problems. Solve each one yourself first — pick the right heap direction, decide its size bound, and reason about complexity — then open the linked answer. Every View answer link jumps to a full multi-language solution on the heap solutions page.
How to practice: The recurring trick is a size-k heap: to find the k largest, keep a min-heap of size k (evict the smallest); to find the k smallest, keep a max-heap of size k. If that feels backwards, re-read priority queues before peeking.
Warm-ups
Q1. Kth largest element in an array. Given an integer array nums and an integer k, return the kth largest element (in sorted order, not the kth distinct). Aim for O(n log k) time using a heap of size k.
Q2. Last stone weight. You have stones with positive integer weights. Each turn, smash the two heaviest together: if equal, both vanish; otherwise the lighter vanishes and the heavier becomes the difference. Return the weight of the last remaining stone (or 0 if none). Use a max-heap.
Core problems
Q3. Top K frequent elements. Given an array nums and integer k, return the k most frequent elements, in any order. Target better than sorting all distinct elements — O(n log k).
Q4. K closest points to origin. Given an array of points [x, y] and integer k, return the k points closest to (0, 0) by Euclidean distance. Use a size-k heap; avoid the square root.
Q5. Merge k sorted lists. Given k sorted arrays, merge them into one sorted array. With N total elements, aim for O(N log k) using a min-heap of the current front of each list.
Challenge
Q6. Find median from a data stream. Design a structure that supports addNum(x) and findMedian() as numbers stream in. Each addNum should be O(log n) and findMedian O(1). Hint: balance two heaps.
Done? Review every solution on the heap answer sheet — even the ones you solved, since the size-k and two-heap patterns repeat constantly in interviews. Then continue to tries.