Heap Pattern: When a Priority Queue Beats Sorting Everything

Whenever a problem asks for the largest, smallest, top k, or next best item while data keeps arriving, a heap should come to mind.

A heap is not about fully sorting everything. It is about maintaining quick access to the most important element.

That distinction matters because many problems do not need a completely sorted result. They only need the current best candidate.

What a Heap Gives You

In a min-heap:

• the smallest element is always at the top

In a max-heap:

• the largest element is always at the top

Typical operations:

• push: O(log n)
• pop: O(log n)
• peek: O(1)

Classic Example: Kth Largest Element

Instead of sorting the full array, keep a min-heap of size k.

import heapq

def find_kth_largest(nums: list[int], k: int) -> int:
    heap: list[int] = []

    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)

    return heap[0]

The heap stores the k largest elements seen so far. The smallest among them is the kth largest overall.

Streaming Problems

Heaps are especially useful when data arrives over time.

Example: continuously track the top 10 largest values from a live stream. Sorting on every update is wasteful. A bounded heap keeps the answer updated incrementally.

Merge K Sorted Lists

This is another classic heap problem. At any moment, the next smallest node among all lists should come first.

The heap lets you compare only the current heads instead of flattening everything.

When a Heap Is Better Than Sorting

Choose a heap when:

• you only need top k
• data arrives incrementally
• you repeatedly need the smallest or largest remaining item
• the answer changes as you process events

Choose sorting when:

• you need the full order anyway
• the data is static and one sort is simplest

Common Mistakes

• Using a heap when a sort is simpler and equally good
• Forgetting whether you need a min-heap or max-heap
• Letting the heap grow larger than necessary in top-k problems
• Ignoring tie-breaking rules for tuples or custom objects

In Python, heapq is a min-heap, so a common max-heap trick is to push negative values.

Complexity

That O(n log k) result is why heaps are so useful for large datasets when k is small.

Practice These Next

• Kth Largest Element in an Array
• Top K Frequent Elements
• Find Median from Data Stream
• Merge K Sorted Lists
• Task Scheduler

Heaps are the right mental tool anytime you want the best item now without paying the cost of total order.