Heap & Priority Queue Pattern

The Heap & Priority Queue pattern uses binary heaps to maintain dynamic collections where the maximum or minimum element is always accessible at the root node in constant time.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The problem asks for the “kth largest”, “kth smallest”, or “top k” elements.
• You need to dynamically retrieve extreme values (minimum or maximum) from a stream of incoming data.
• The task involves merging multiple sorted lists or streams (e.g. Merge K Sorted Lists).
• You are optimizing a search that requires picking the “best” candidate at each step (like Dijkstra’s algorithm).

How It Works

A binary heap is a complete binary tree that satisfies the heap property:

• Min-Heap: The value of each node is greater than or equal to the value of its parent. The smallest element is always at the root.
• Max-Heap: The value of each node is less than or equal to the value of its parent. The largest element is always at the root.

For example, to track the 3 largest numbers in a stream:

1. Maintain a min-heap of size 3.
2. If the heap has fewer than 3 elements, push the incoming number.
3. If the heap is full, compare the incoming number against the root (the minimum of the top 3). If the number is larger, pop the root and push the new number.
4. The root of the min-heap represents the 3rd largest element.

Complexity, With Caveats

• Time Complexity: O(1) to inspect (peek) the top element. O(log n) to insert (push) or remove (pop) an element, as the heap must restore its structure by bubbling values up or down.
• Space Complexity: O(n) to store elements in the heap array.

Minimal Code Template

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

public class HeapTemplate {
    // Find Kth Largest Element using Min-Heap
    public int findKthLargest(int[] nums, int k) {
        // min-heap to store the k largest elements
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // remove the smallest of the k elements
            }
        }
        return minHeap.peek(); // the top of the heap is the kth largest
    }
}

import heapq


# Find Kth Largest Element using Min-Heap
def find_kth_largest(nums: list[int], k: int) -> int:
    # min-heap to store the k largest elements
    min_heap = []

    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)  # remove the smallest of the k elements

    return min_heap[0]  # top of heap is the kth largest

#include <vector>
#include <queue>

class HeapTemplate {
public:
    // Find Kth Largest Element using Min-Heap
    int findKthLargest(const std::vector<int>& nums, int k) {
        // min-heap
        std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

        for (int num : nums) {
            minHeap.push(num);
            if (minHeap.size() > k) {
                minHeap.pop(); // remove the smallest
            }
        }
        return minHeap.top();
    }
};

Where This Pattern Falls Short

• Random access or updates: Heaps only expose the root element. Searching for a specific value in a heap takes O(n) linear time because elements are not sorted across branches.
• Index-based queries: If you need to retrieve elements by index (e.g. “what is the 5th element in insertion order”), a heap cannot help; you must use a List or balanced BST.

Related Patterns, Compared

• Binary Search: choose this instead when the input data is static and sorted, as it allows searching in O(log n) time with O(1) space.
• Sort: choose this instead when you need to sort the entire array once and do not need to process incoming streams of elements.

Frequently Asked Questions

Why does Python’s heapq only support min-heaps? Python’s standard library design chose to implement only min-heaps. To build a max-heap in Python, you must negate the values before pushing them (heapq.heappush(heap, -value)) and negate them again when popping.

What is the difference between Heapify and individual insertions? Heapifying an existing array of size n takes O(n) time using bottom-up sift-down operations. Inserting n elements one by one into an empty heap takes O(n log n) time.

What does this pattern test in interviews? It tests your ability to optimize sorting-based problems from O(n log n) to O(n log k) by containing the heap search space.