Heap and Priority Queue

Intuition

A priority queue is a container where you can always take out the "best" element (smallest or largest) quickly. The usual implementation is a binary heap: a complete binary tree in which every parent is no larger than its children (a min-heap; flip the comparison for a max-heap). The heap property is deliberately weak. It says nothing about siblings or cousins, only that each path from the root down is sorted, and that weakness is what makes updates cheap. The minimum always sits at the root.

Because the tree is complete (every level full except the last, which fills from the left), it fits in a plain array with no pointers. With 0-based indices, the children of i are 2i + 1 and 2i + 2, and its parent is (i - 1) // 2.

The two core moves:

• Sift up (after push): append the new value as the last leaf, then swap it with its parent while it is smaller. O(log n).
• Sift down (after pop): move the last leaf into the root, then repeatedly swap it with its smaller child until both children are larger. O(log n).

Building a heap from n values can be done in O(n), not O(n log n): sift down every internal node from the last one up to the root. Most nodes sit near the bottom and move only a step or two, and the total work sums to linear. (Inserting the values one by one, by contrast, can cost O(n log n).)

Library support:

• Python: heapq turns a list into a min-heap: heappush, heappop, heapify (O(n)), heapreplace (pop then push), heappushpop, nlargest, nsmallest. For a max-heap, push negated keys. Tuples compare element by element, so (priority, tiebreak, item) works.
• Java: PriorityQueue is a min-heap by default; pass Collections.reverseOrder() or a comparator for other orders.
• C++: priority_queue is a max-heap by default; use priority_queue<T, vector<T>, greater<T>> for a min-heap.

Other heap types (binomial, pairing, leftist, Fibonacci) offer faster merging or decrease-key, but they are beyond interview scope.

When to use it in interviews / OAs

• "k largest / k smallest / k-th largest / top k": keep a heap of size k. Counterintuitively, the k largest values live in a min-heap, so the weakest of them can be evicted in O(log k).
• Repeatedly take the best of a changing set: CPU and task schedulers, meeting rooms (min-heap of end times), event simulations, Dijkstra and Prim.
• Merging sorted streams: merge k sorted lists, k-th smallest in a sorted matrix, k pairs with the smallest sums, smallest range covering k lists.
• Running statistics: median of a data stream with two heaps; the same idea maintains "the k-th largest so far" when k changes by small steps.
• Greedy with regret: take items greedily and, when a constraint breaks, drop the worst item taken so far (course scheduling with deadlines, minimum refueling stops, maximizing capital).
• Repeatedly merge the two smallest: Huffman coding and "minimum cost to connect ropes" (see the Huffman coding article).

Template

A min-heap from scratch. Interviewers sometimes ask for exactly this, and it is the best way to remember why each operation is O(log n).

class MinHeap:
    def __init__(self, items: list[int] | None = None) -> None:
        self.a = list(items or [])
        for i in range(len(self.a) // 2 - 1, -1, -1):  # O(n) heapify: sift down each internal node.
            self._sift_down(i)

    def __len__(self) -> int:
        return len(self.a)

    def peek(self) -> int:
        return self.a[0]

    def push(self, x: int) -> None:
        self.a.append(x)  # New leaf at the end keeps the tree complete.
        self._sift_up(len(self.a) - 1)

    def pop(self) -> int:
        a = self.a
        a[0], a[-1] = a[-1], a[0]  # Move the last leaf to the root, then remove the old root.
        top = a.pop()
        if a:
            self._sift_down(0)
        return top

    def _sift_up(self, i: int) -> None:
        a = self.a
        while i > 0:
            parent = (i - 1) // 2
            if a[parent] <= a[i]:
                break
            a[parent], a[i] = a[i], a[parent]
            i = parent

    def _sift_down(self, i: int) -> None:
        a, n = self.a, len(self.a)
        while True:
            smallest, left, right = i, 2 * i + 1, 2 * i + 2
            if left < n and a[left] < a[smallest]:
                smallest = left
            if right < n and a[right] < a[smallest]:
                smallest = right
            if smallest == i:
                return
            a[i], a[smallest] = a[smallest], a[i]  # Swap with the smaller child.
            i = smallest


h = MinHeap([5, 3, 8, 1])
h.push(2)
assert [h.pop() for _ in range(len(h))] == [1, 2, 3, 5, 8]

The everyday heapq patterns: a size-k heap for top-k, a heap of "next candidates" for k-way merging, and negation for a max-heap.

import heapq


def top_k_largest(nums: list[int], k: int) -> list[int]:
    heap: list[int] = []  # Min-heap holding the k largest values seen so far.
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:  # x beats the weakest of the current top k.
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)


def merge_k_sorted(lists: list[list[int]]) -> list[int]:
    heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(heap)
    out = []
    while heap:
        val, i, j = heapq.heappop(heap)  # The list index i breaks ties between equal values.
        out.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return out


assert top_k_largest([3, 1, 5, 12, 2, 11], 3) == [12, 11, 5]
assert merge_k_sorted([[1, 4, 5], [1, 3, 4], [], [2, 6]]) == [1, 1, 2, 3, 4, 4, 5, 6]

max_heap: list[int] = []
for x in (3, 1, 4, 1, 5):
    heapq.heappush(max_heap, -x)  # heapq is a min-heap: store negatives for a max-heap.
assert -max_heap[0] == 5

Two heaps for a running median. low keeps the smaller half as a max-heap, high keeps the larger half as a min-heap, and their tops are the middle elements. Every insertion passes through low and then high, which keeps the halves ordered, and a final rebalance keeps the sizes within one.

import heapq


class MedianFinder:
    def __init__(self) -> None:
        self.low: list[int] = []  # Max-heap (negated) with the smaller half.
        self.high: list[int] = []  # Min-heap with the larger half.

    def add(self, x: int) -> None:
        heapq.heappush(self.low, -x)
        heapq.heappush(self.high, -heapq.heappop(self.low))  # Route x through low so every low <= every high.
        if len(self.high) > len(self.low):  # Keep len(low) == len(high) or len(high) + 1.
            heapq.heappush(self.low, -heapq.heappop(self.high))

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


mf = MedianFinder()
mf.add(1)
mf.add(2)
assert mf.median() == 1.5
mf.add(3)
assert mf.median() == 2.0

No decrease-key or arbitrary delete? heapq cannot update an element in place. Use lazy deletion: push a fresh entry with the new priority and, when popping, skip entries that are stale (for example, in Dijkstra, if d > dist[u]: continue). For deletions, keep a counter of values waiting to be removed and discard them when they reach the top.

Complexity

Operation	Time
peek min	O(1)
push, pop	O(log n)
heapify n items	O(n)
top k of n items with a size-k heap	O(n log k) time, O(k) space
merge k sorted lists of total length N	O(N log k)
running median: add / query	O(log n) / O(1)

Heap sort (heapify, then pop n times) is O(n log n) in place but not stable, and in interviews you would simply call the built-in sort.

Common pitfalls

• Wrong heap direction. Python's heapq and Java's PriorityQueue are min-heaps; C++'s priority_queue is a max-heap. Negating keys is easy to get half right: negate on push and on read.
• Uncomparable payloads. heappush(h, (dist, node)) crashes or misbehaves if two distances tie and the nodes cannot be compared. Add a unique tiebreaker such as an index or counter: (dist, idx, node).
• Treating the array as sorted. Only heap[0] is guaranteed; heap[1] is not necessarily the second smallest.
• Mutating elements in place. Changing a priority inside the list silently breaks the invariant; push a new entry instead (lazy deletion).
• Popping from an empty heap. Check if heap first.
• Using a max-heap for "k largest". It works but costs O(n log n); the size-k min-heap is the O(n log k) answer interviewers expect.

Interview variations

• K-th largest element (also in a stream), top k frequent elements, k closest points to the origin (max-heap of size k on distance).
• Merge k sorted lists, k-th smallest element in a sorted matrix, find k pairs with smallest sums.
• Find median from a data stream, sliding window median (two heaps plus lazy deletion).
• Meeting rooms II, task scheduler, single-threaded CPU, process tasks using servers: heaps of free resources and pending work, usually keyed by time.
• Reorganize string: always place the most frequent remaining character that differs from the previous one.
• Greedy with a heap: maximize capital, minimum refueling stops, course schedule with deadlines, furthest building you can reach.
• Graph algorithms: Dijkstra's shortest paths and Prim's MST are priority-queue algorithms.