ReviseAlgo Logo

Heaps & Priority Queues

Practice & Revision

Heap and Priority Queue pattern recognition decision tree, cheat sheet, and Top 15 must-solve heap interview problems.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

This section serves as your comprehensive reference and practice guide for Heaps & Priority Queues. Master these templates, review the decision tree, and solve the curated Top 15 interview problems to prepare for technical interviews.

2. Heap Pattern Decision Tree

Use this flow chart to determine the correct heap configuration based on your algorithm:

3. Revision Cheat Sheet

Priority Queue API Cross-Reference

LanguageDefault Heap TypeCustom Comparator Syntaxpush / pop
JavaMin-Heapnew PriorityQueue<>((a, b) -> b - a) (Max-Heap)pq.offer(x) / pq.poll()
PythonMin-HeapNegate elements to simulate Max-Heapheapq.heappush(h, x) / heappop(h)
C++Max-Heappriority_queue, greater> (Min-Heap)pq.push(x) / pq.pop()

Parent-Child Index Formulas (0-indexed Array)

  • Parent: (i - 1) / 2
  • Left Child: 2 i + 1
  • Right Child: 2 i + 2

    • 4. Top 15 Must-Solve Heap Problems

    Note: Interactive Practice Table Available: Switch to the Practice Problems tab at the top of this lesson to interactively solve, track completion, watch video solutions, and take notes on all 15 must-solve heap interview problems!

    5. Problem-Solving Framework

    When coding Heap solutions, follow this 3-step checklist:

    1. Verify Default Heap Directions: - Remember: Java/Python are Min-Heaps by default; C++ is a Max-Heap. Always verify you configured custom comparators correctly to avoid direction flips. 2. Constrain Heap Size: - Don't push all N items. If you only need the top K, push elements and immediately pop when size exceeds K. This saves memory and keeps operations fast. 3. Use Heaps to Avoid Re-Sorting: - If a stream of numbers is updated dynamically and you need the largest/smallest values, do not sort the array repeatedly (O(N² log N)). A Heap maintains this priority in O(log N) per addition.

    6. Quiz

    Question 1: In 'K Closest Points to Origin', why do we use a Max-Heap of size K instead of a Min-Heap? Answer: Because we want the K closest points (minimum distance). In a Max-Heap of size K, the root stores the maximum distance currently in our list. If we find a point closer than the root, we pop the root (evicting the furthest candidate) and push the new point, keeping the closest points.
    Question 2: What occurs when we insert into a heap that is at capacity? Answer: If it is a dynamic container (like Java's PriorityQueue), it resizes by doubling its backing array (O(N) copies, amortized to O(1)). If size is restricted via popping, we pop the root first, then insert.
    Question 3: In C++, how do you configure std::priority_queue to behave as a Min-Heap? Answer: Define it as: std::priority_queue, std::greater> pq;.
    Question 4: What is the optimal time complexity to connect N sticks of varying lengths into one? Answer: O(N log N) time. At each step, we pop the two shortest sticks from a Min-Heap, sum them, add the cost, and push the combined stick back. This takes N-1 heap steps.
    Question 5: Why is Dijkstra's algorithm implemented with a Min-Heap instead of a Queue? Answer: Because Dijkstra's must always explore the vertex with the shortest current path first. A Min-Heap retrieves this vertex in O(1) time, optimizing shortest path evaluations.