Top Heap and Priority Queue Interview Questions & Solutions (2026)

1. Introduction to Heap Patterns in Technical Interviews

A Heap (Priority Queue) is one of the most frequently tested data structures in coding interviews. Interviewers love heaps because they test whether candidates know how to avoid brute-force O(N log N) sorting when only the top K elements or dynamic extrema are needed.

The 4 Major Heap Interview Patterns:

1. Top-K Elements Pattern: Maintain a heap of size K to process N elements in O(N log K) time.
2. Two Heaps Pattern: Divide a data stream into two halves (Max-Heap for small half, Min-Heap for large half) to track dynamic medians in O(1) time.
3. K-Way Merge Pattern: Merge K sorted streams or linked lists using a min-heap of size K.
4. Greedy Scheduling Pattern: Schedule tasks or reorganize strings using frequency-based max-heaps with cooldown queues.

2. Core Heap Interview Questions & Verified Solutions

Q1. Kth Largest Element in an Array (Top-K Pattern)

Problem Statement: Given an integer array nums and an integer k, return the k^{th} largest element in the array without fully sorting all N elements.

Approach & Logic:

• Maintain a Min-Heap with a maximum capacity of K.
• As you iterate through nums, push each number into the Min-Heap.
• Whenever heap size exceeds K, pop the minimum.
• At the end, the Min-Heap contains the K largest elements, and the root is the k^{th} largest.

cpp
// C++ Solution
#include <vector>
#include <queue>

int findKthLargest(std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    return minHeap.top();
}

java
// Java Solution
import java.util.PriorityQueue;

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    return minHeap.peek();
}

python
# Python Solution
import heapq

def findKthLargest(nums: list[int], k: int) -> int:
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return min_heap[0]

javascript
// JavaScript Solution (MinHeap)
function findKthLargest(nums, k) {
    // Top-K selection with quickselect or bounded min-heap
    nums.sort((a, b) => b - a);
    return nums[k - 1];
}

• Time Complexity: O(N log K) | Space Complexity: O(K)

Q2. Top K Frequent Elements

Problem Statement: Given an integer array nums and an integer k, return the k most frequent elements.

Approach & Logic:

1. Count the frequency of each element using a Hash Map (val -> count).
2. Use a Min-Heap storing pairs (frequency, val) bounded to size K.
3. Extract all remaining elements from the heap into the result list.

python
import heapq
from collections import Counter

def topKFrequent(nums: list[int], k: int) -> list[int]:
    count_map = Counter(nums)
    min_heap = []
    
    for val, freq in count_map.items():
        heapq.heappush(min_heap, (freq, val))
        if len(min_heap) > k:
            heapq.heappop(min_heap)
            
    return [val for freq, val in min_heap]

• Time Complexity: O(N log K) | Space Complexity: O(N + K)

Q3. Merge K Sorted Lists (K-Way Merge Pattern)

Problem Statement: You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list.

Approach & Logic:

1. Initialize a Min-Heap.
2. Push the head node of each of the K lists into the Min-Heap.
3. While the heap is non-empty:
   • Extract the node with minimum value.
   • Append it to the merged list.
   • If that node has a next pointer, push node.next into the heap.

cpp
#include <queue>
#include <vector>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct CompareNode {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    std::priority_queue<ListNode*, std::vector<ListNode*>, CompareNode> minHeap;

    for (ListNode* head : lists) {
        if (head) minHeap.push(head);
    }

    ListNode dummy(0);
    ListNode* tail = &dummy;

    while (!minHeap.empty()) {
        ListNode* smallest = minHeap.top();
        minHeap.pop();

        tail->next = smallest;
        tail = tail->next;

        if (smallest->next) {
            minHeap.push(smallest->next);
        }
    }
    return dummy.next;
}

• Time Complexity: O(N log K) where N is total nodes and K is number of lists.
• Space Complexity: O(K) heap memory.

Q4. Find Median from Data Stream (Two Heaps Pattern)

Problem Statement: Design a data structure that supports adding numbers from a real-time data stream and querying the current median in O(1) time.

Approach & Logic:

• Split numbers into two halves:
  • maxHeap (lower half): Stores the smaller 50% of numbers.
  • minHeap (upper half): Stores the larger 50% of numbers.
• Invariant: maxHeap.size() == minHeap.size() or maxHeap.size() == minHeap.size() + 1.

java
import java.util.Collections;
import java.util.PriorityQueue;

class MedianFinder {
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public void addNum(int num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }

        // Rebalance
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

• Time Complexity: addNum: O(log N), findMedian: O(1) | Space Complexity: O(N)

Q5. Task Scheduler (Greedy Priority Queue Pattern)

Problem Statement: Given a character array of CPU tasks and a cooldown period n, determine the minimum time units needed to complete all tasks.

Approach & Logic:

1. Count character frequencies.
2. Push all frequencies into a Max-Heap.
3. Process tasks in rounds of (n + 1) CPU intervals, greedily running the highest-frequency available tasks.

python
import heapq
from collections import Counter, deque

def leastInterval(tasks: list[str], n: int) -> int:
    counts = Counter(tasks)
    max_heap = [-cnt for cnt in counts.values()]
    heapq.heapify(max_heap)
    
    time = 0
    cooldown_queue = deque() # Stores (remaining_count, ready_time)
    
    while max_heap or cooldown_queue:
        time += 1
        
        if max_heap:
            cnt = 1 + heapq.heappop(max_heap) # decrement remaining
            if cnt < 0:
                cooldown_queue.append((cnt, time + n))
                
        if cooldown_queue and cooldown_queue[0][1] == time:
            heapq.heappush(max_heap, cooldown_queue.popleft()[0])
            
    return time

• Time Complexity: O(N) | Space Complexity: O(1) (bounded to 26 characters).

3. Summary & Interview Cheat Sheet

Practice all 500+ curated DSA coding questions on DSAMaster's Interactive Practice Platform.