Heaps & Priority Queues 101

What a heap is and when to use one

Always know the smallest

A heap is a binary tree stored in an array where every parent is no larger than its children (a min-heap). That single rule means the smallest element is always at index 0. Pushing a new element or popping the smallest takes O(log n), and peeking at the smallest is O(1). A priority queue is the abstract idea ("give me the most important item next"); a heap is how it is almost always implemented.

Python's heapq module works on a plain list and gives a min-heap only. For a max-heap, push negated values (-x) or tuples with a negated key.

Signals in a problem statement

• "k-th largest / k-th smallest", "top k frequent", "k closest points".
• "Repeatedly take the two largest (or smallest) and combine them" — a simulation that always needs the current extreme.
• "Merge k sorted lists or arrays".
• "Median of a stream" — two heaps.
• "Schedule tasks", "choose projects with limited capital", "meeting rooms needed" — greedy choices that always pick the best currently available option.
• Shortest paths with weights (Dijkstra), covered in the Graphs card.

Heap or sort?

If you need everything in order once, sorting is simpler. A heap wins when items arrive over time, when you only need the top k of a large n (O(n log k) instead of O(n log n)), or when the set changes between choices. Saying this trade-off out loud is a mark of maturity.

Mental model

Think of a hospital emergency ward: patients arrive in any order, but the doctor always sees the most urgent one next. The heap is the triage desk.

Core patterns with templates

1. Basic operations

import heapq

h = []
heapq.heappush(h, 5)
heapq.heappush(h, 2)
smallest = heapq.heappop(h)   # 2
heapq.heapify(h)              # O(n) for an existing list
top = h[0] if h else None     # peek

2. Size-k heap for the k-th largest

Keep a min-heap of the k largest values seen; its top is the answer.

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

Example: [3, 2, 1, 5, 6, 4], k = 2 keeps [5, 6], answer 5.

3. Max-heap by negation (simulation)

def last_stone_weight(stones):
    h = [-s for s in stones]
    heapq.heapify(h)
    while len(h) > 1:
        a, b = -heapq.heappop(h), -heapq.heappop(h)
        if a != b:
            heapq.heappush(h, -(a - b))
    return -h[0] if h else 0

4. Tuples as keys

def k_closest(points, k):
    return heapq.nsmallest(k, points, key=lambda p: p[0] * p[0] + p[1] * p[1])

When pushing tuples yourself, add a tie-breaker (such as an index) before any object that cannot be compared: (dist, i, point).

5. Two-phase greedy: unlock, then pick the best

Sort options by their requirement; as your resources grow, push every newly affordable option into a max-heap, then take the best one.

def max_capital(k, w, profits, capital):
    projects = sorted(zip(capital, profits))
    h, i = [], 0
    for _ in range(k):
        while i < len(projects) and projects[i][0] <= w:
            heapq.heappush(h, -projects[i][1])
            i += 1
        if not h:
            break
        w -= heapq.heappop(h)
    return w

Complexity, mistakes and edge cases

Complexity

Space is O(k) for a bounded heap, O(n) otherwise.

Common mistakes

• Forgetting Python only has a min-heap. For the largest values, negate on push and on pop.
• Using a max-heap of size n for the k-th largest when a min-heap of size k is cheaper and is what the interviewer is fishing for.
• Comparing uncomparable objects. Tuples with equal first elements compare the second element; if that is a ListNode or dict, Python raises TypeError. Insert a counter as a tie-breaker.
• Modifying a heap list directly (for example h[3] = 7) without restoring the heap property.
• Popping from an empty heap. Check if h first, especially in simulations.
• Taking square roots for distance comparisons. Squared distances order the same way and avoid floating point.

Edge cases

k equal to n, k = 1, duplicate values, negative numbers, an empty heap at the end of a simulation, and projects that can never be afforded.

Quickselect as an alternative

For a one-off k-th largest on an array, quickselect partitions around a random pivot and recurses into one side only, averaging O(n) time. It is worth mentioning as a follow-up, but the heap solution is safer to code under pressure and is perfectly acceptable for most interviews.

Variations and practise

How interviewers twist it

• Top k frequent elements. Count with a Counter, then keep a size-k heap of (count, value). A bucket sort by frequency gives O(n) as a follow-up.
• Merge k sorted lists. Push the head of each list as (value, list_index, node); pop the smallest, push its successor. O(N log k).
• Median of a data stream. A max-heap for the lower half and a min-heap for the upper half, kept within one element of each other in size. The median is the top of one heap or the average of both tops.
• Task scheduling with cooldown. A max-heap of remaining counts plus a queue of tasks waiting out their cooldown.
• Meeting rooms. Sort by start time and keep a min-heap of end times; the heap size is the number of rooms in use.
• Lazy deletion. When items must be removed from the middle, mark them as deleted and discard them when they reach the top.

How to explain it

Say what the heap holds and what its top means: "a min-heap of the k largest values so far; its top is the k-th largest". That phrasing also makes the O(n log k) cost obvious.

Practise

The problems below cover a size-k heap, a max-heap simulation, closest points with a distance key, and a two-phase greedy that unlocks options as capital grows. For each one, decide first whether you need a min-heap or a max-heap, and what the tie-breaker is.