QuizzesHeaps & Priority Queues
intermediate
dsa

Heaps & Priority Queues

Min-heap, max-heap, Kth largest, Top K elements, merge K lists, and Find Median from Data Stream.

25 minutes 10 questions Pass at 70%
Time Limit
25 minutes - timer starts when you begin
Change Answers Freely
Revisit and change any answer before submitting
Full Review After Submit
Correct answers and explanations shown for every question
Auto-submit on timeout
Quiz submits automatically when time runs out

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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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²)