Heaps & Priority Queues

A priority queue answers one question efficiently: “What is the next most important item?” The priority might be the smallest number, largest score, earliest deadline, or shortest tentative distance. A heap is the array-backed data structure that makes that queue fast.

The trade-off is focused. A heap is not sorted; it only guarantees that the best item is at the top. That is exactly enough for top-K, scheduling, streaming medians, merging sorted lists, and shortest-path algorithms.

The mental model

A binary heap is a complete binary tree stored in an array. For a min-heap, every parent is less than or equal to its children, so the minimum is always at index 0. In Python, heapq implements a min-heap.

import heapq

heap = [5, 1, 9, 3]
heapq.heapify(heap)        # O(n), rearranges in place
heap[0]                    # O(1) peek at the smallest
heapq.heappush(heap, 2)    # O(log n)
smallest = heapq.heappop(heap)  # O(log n)

heappush bubbles a new item up until the heap property is restored. heappop removes the root, moves the last item to the root, then bubbles it down. The height of a complete binary tree is O(log n), so both operations are O(log n). Peeking is O(1) because the best item is already at the root.

Python has no max-heap API in heapq. Negate numeric priorities when you need the largest item first:

max_heap = []
for x in [5, 1, 9, 3]:
    heapq.heappush(max_heap, -x)

largest = -heapq.heappop(max_heap)

When each element has a priority and a payload, push tuples like (priority, value). Python compares tuples lexicographically, so ties fall through to the next field. Add a counter if payloads are not comparable.

Pattern recognition

Variations

Worked problems

Notice the difference between “sort once” and “keep the right frontier while you scan.” Heaps shine in the second shape.

import heapq


def find_kth_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

from collections import Counter
import heapq


def top_k_frequent(nums, k):
    counts = Counter(nums)
    heap = []

    for value, freq in counts.items():
        heapq.heappush(heap, (freq, value))
        if len(heap) > k:
            heapq.heappop(heap)

    return [value for freq, value in heap]

import heapq


class MedianFinder:
    def __init__(self):
        self.low = []   # max-heap via negatives
        self.high = []  # min-heap

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))

        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def find_median(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

The classic pitfall