Heaps & Priority Queues
Min-heap, max-heap, Kth largest, Top K elements, merge K lists, and Find Median from Data Stream.
Questions in this quiz
10 questions on Heaps & Priority Queues. Work through them here, then start the quiz to answer them and see your score.
1.What is a min-heap and what are the time complexities of its core operations?
- AA balanced BST — O(log n) for all operations including peek
- BA hash table — O(1) average for all operations
- CA complete binary tree where each node ≤ its children — O(log n) insert/delete, O(1) peek min
- DA sorted array — O(1) min, O(n log n) insert
2.When should you use a heap instead of sorting the full array?
- ANever — sorting is always better
- BWhen you need to find the median of a static array
- CWhen the data is already sorted
- DWhen you only need the top k elements or when elements arrive in a stream and you repeatedly need the current min/max
3.What does this code compute for nums = [3, 2, 1, 5, 6, 4], k = 2?
PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int n : nums) { pq.offer(n); if (pq.size() > k) pq.poll(); } System.out.println(pq.peek());- A5
- B4
- C3
- D6
4.What is the time complexity of building a heap from n elements using bottom-up heapify?
- AO(log n)
- BO(n²)
- CO(n)
- DO(n log n)
5.Find Median from Data Stream: integers arrive one by one, return current median at any point. What is the optimal structure?
- AA BST maintaining sorted order
- BA regular array, sorted on each median query
- CTwo heaps: a max-heap for the lower half and a min-heap for the upper half, kept balanced in size
- DA sorted ArrayList — insert in sorted position each time
6.Merge K Sorted Arrays — what is the role of the heap in this approach?
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); for (int i = 0; i < lists.length; i++) { if (lists[i].length > 0) pq.offer(new int[]{lists[i][0], i, 0}); } // Extract min, advance that list's pointer, insert next element from that list- ASort all elements at once — O(N log N) where N is total elements
- BAlways extract the current global minimum efficiently — O(N log k) total
- CFind the kth smallest element across all arrays
- DFind the intersection of all arrays
7.Top K Frequent Elements: given n numbers, find the k most frequent. What is the most efficient approach?
- ASort by frequency: O(n log n)
- BHashMap for counts + min-heap of size k (keyed by count): O(n log k)
- CBucket sort by frequency since max frequency ≤ n: O(n)
- DBoth B and C are valid; C is faster for large n
8.K Closest Points to Origin — which heap type and why?
- AMin-heap of all points by distance, extract k times: O(n + k log n)
- BMax-heap of size k — evict the farthest point whenever size exceeds k: O(n log k)
- CSort all points by distance: O(n log n)
- DBFS outward from the origin
9.What is the key difference between a heap and a BST for ordered operations?
- AHeap supports O(1) search; BST does not
- BHeap: O(1) min/max peek but no efficient search or range queries; BST: O(log n) for search, predecessor, successor, and range queries
- CBST is always faster for all operations
- DThey have identical performance characteristics
10.What is the time complexity advantage of a heap over sorting for finding the kth smallest in a stream of n elements?
- AHeap maintains k elements: O(n log k); sorting requires all n elements to be available first: O(n log n)
- BNo advantage — both are O(n log n)
- CThey have the same complexity for streams
- DHeap is O(n); sorting is O(n²)