Priority Queue / Heap

A heap answers one question — what is the smallest thing here? — and answers it instantly, while still accepting new items cheaply. It answers nothing else. You cannot ask it what the second smallest is, whether some value is present, or what the items are in order.

That narrowness is the point. Sorting gives you everything and costs O(n log n) up front. A heap gives you only the extreme, and lets you take it repeatedly while the data is still arriving.

An array pretending to be a tree#

A binary heap is a complete binary tree — every level full except possibly the last, which fills left to right. That shape means it never needs pointers. Store it in an array and the structure is arithmetic:

parent(i) = (i - 1) / 2
left(i)   = 2i + 1
right(i)  = 2i + 2

The invariant is deliberately weak: every parent is no larger than its children (for a min-heap). That is all. Siblings are unordered, cousins are unordered, and the array is nowhere near sorted.

The weakness is what makes it fast. A sorted array has to maintain a relationship between every pair of elements, so inserting one item can disturb all of them. A heap only maintains a relationship along each parent-child edge, so an insert can only disturb one path — and there are just log n of those steps to fix.

Step through it watching both halves at once. They are not two structures; the tree is a drawing of the array, and index 4 is under index 1 because 4’s parent is (4-1)/2 = 1 and for no other reason. The two repairs are mirror images:

• Push puts the new value at the end of the array — the only position that keeps the tree complete — then sifts up while it is smaller than its parent.
• Pop takes the root, moves the last element into the hole so nothing has to shift, then sifts down, always swapping with the smaller child.

That last detail is a real bug source. Swapping with either child, or with the larger one, leaves the two children out of order with each other and quietly corrupts the heap.

function push(v):
    append v to the end
    i = last index
    while i > 0 and a[parent(i)] > a[i]:
        swap a[parent(i)], a[i]
        i = parent(i)

function pop():
    top = a[0]
    a[0] = last element;  remove the last element

    i = 0
    loop:
        // children may not exist; take the smallest of whatever does
        smallest = index of min(a[i], a[left(i)], a[right(i)])
        if smallest == i:  break
        swap a[i], a[smallest]
        i = smallest

    return top

The interactive heap snippet builds both of these in Go, line by line, as up and down on a plain slice — worth stepping through once, because every other use on this page treats the structure as a black box.

What it costs#

• Peek — O(1). The answer is a[0]; nothing is computed.
• Push and pop — O(log n), one root-to-leaf path.
• Build from an existing array — O(n), not O(n log n). Sifting down from the middle backwards is cheaper than n pushes, because most elements are near the bottom and barely move. Worth knowing: it is a common follow-up, and the intuitive answer is wrong.
• Search for an arbitrary value — O(n). The heap has no idea where anything is.
• Delete an arbitrary value — O(n) to find it first, so in practice you do not. See lazy deletion below.

Top k, and the heap that faces the wrong way#

This is the pattern that makes heaps worth learning, and the setup is counter-intuitive enough that it is worth saying slowly:

To keep the k largest items, use a min-heap of size k.

The heap holds the current best k. Its root is the weakest member of that set — which is exactly the one to compare a newcomer against. If the new item beats the root, the root is evicted and the new item takes its place; if not, the new item was never going to qualify. Either way it is one comparison and at most one O(log k) update.

heap = empty min-heap

for x in items:
    push x onto heap
    if size(heap) > k:
        pop()             // evict the smallest: it no longer qualifies

// the heap now holds the k largest, with the k-th largest at the root

The cost is O(n log k) time and O(k) space. Compare that with sorting everything — O(n log n) time and O(n) space — and the gap grows exactly when it matters: n in the millions, k in the tens. It also works on a stream, where sorting is not even available because you never hold all of n.

K Closest Points to Origin is this with the comparison inverted: a max-heap of size k keyed on distance, evicting the farthest. Two details worth mentioning out loud — compare squared distances rather than calling sqrt, since the ordering is identical and the square root is both slower and lossy; and if the language only offers a min-heap, negate the key.

When not to use a heap for this#

If you have the whole array in memory and may rearrange it, quickselect finds the k-th element in O(n) average time, beating O(n log k). The quickselect snippet has the details.

The trade is honest and worth stating in an interview: quickselect is faster on average but O(n²) in the worst case, mutates the input, and needs all of it up front. The heap is predictable, non-destructive, and works on a stream. If the problem says “stream” or “as data arrives”, the heap is the only one of the two that applies.

Merging k sorted sequences#

Merge k Sorted Lists is the other classic. Merging two sorted lists needs only a comparison; merging k needs to know which of k current heads is smallest, and that is a heap.

heap = min-heap of the first node of each list, keyed by value

while heap not empty:
    node = pop()
    append node to the output
    if node has a next:
        push node.next

The heap never holds more than k items, so each of the N total elements costs O(log k) to pass through: O(N log k), with O(k) space. The naive alternative — concatenate everything and sort — is O(N log N), and merging pairwise one list at a time is worse still, because early lists get re-scanned on every merge.

Two heaps for a running median#

Find Median from Data Stream is the problem that makes heaps look clever, and the trick is just to split the data in half:

• A max-heap holds the lower half, so its root is the largest of the small values.
• A min-heap holds the upper half, so its root is the smallest of the large values.

Those two roots sit either side of the median. If the sizes are equal the median is their average; if one heap is allowed to run one larger, the median is its root.

Every insert is: push onto the appropriate side, then rebalance if the sizes differ by more than one by moving one element across. Both steps are O(log n), and reading the median is O(1) — which is the whole reason to do it this way rather than keeping a sorted list.

The bug to watch for is inserting into the wrong half. Push onto the max-heap when the value is at most its root, otherwise onto the min-heap — then rebalance. Rebalancing after the fact is what keeps the invariant simple: everything in the low heap is ≤ everything in the high heap.

Greedy scheduling#

A heap is the natural companion to a greedy rule of the form “always take the most X”. Task Scheduler is the example here: with a cooldown between identical tasks, the task with the most remaining copies is the one to run first, because leaving it until later is what forces idle time at the end.

The heap holds remaining counts; each round pops up to n + 1 distinct tasks, decrements them, and pushes back whatever still has copies left. The heap is doing one job — answering “which task is most urgent right now” after every change.

Task Scheduler also has a closed-form counting solution that is O(n) and shorter. Both are worth knowing; the heap version is the one that generalises when the rules get more complicated.

What a heap cannot do#

Reaching for a heap when you actually need order is a common mis-step. It does not support:

• Finding or deleting an arbitrary element. The standard workaround is lazy deletion — mark items dead in a separate set, and discard them as they surface at the root. It keeps the cost logarithmic at the price of a heap that can hold stale entries.
• Iterating in sorted order. Popping everything gives you that, but it destroys the heap and costs O(n log n) — at which point you should have sorted.
• Updating a key in place, without an index map from value to position. Many problems sidestep this by pushing a new entry and lazily ignoring the outdated one.

If you need ordered traversal, range queries, or predecessor/successor, you want a balanced BST or a sorted container instead.

Language notes#

The default direction differs between languages, and getting it backwards produces answers that look plausible:

• Python — heapq is a min-heap only. For a max-heap, push -x, or push tuples (-key, item). Tuples compare element by element, which is how you attach a payload to a key.
• C++ — std::priority_queue is a max-heap by default. This is the exact opposite of Python, and it catches people who switch between them.
• Java — PriorityQueue is a min-heap; pass a comparator for anything else.
• Go — container/heap is an interface you implement, which is what the snippet above does by hand.

When a heap holds tuples, decide what happens on a tie. In Python, equal keys fall through to comparing the payload, which throws if the payload is not comparable — the usual fix is to insert a counter as a tiebreaker.

Recognising it#

Reach for a heap when:

• The problem says top k, k closest, k largest, or k-th something — and especially when it also says stream.
• You need the minimum or maximum repeatedly, with the data changing in between. A single min is just a scan; it is the repeatedly that earns the structure.
• You are merging several sorted sequences.
• A greedy rule needs “the most urgent remaining item” after every step. This is also why Dijkstra is BFS with a heap in place of the queue.
• You need a running statistic over a stream that depends on order — the median being the standard case.

And the check that stops the wrong choice: do you actually need the ordering, or just the extreme? If it is the ordering, sort. If you need it once rather than repeatedly, scan.

Summary#

A heap is an array with one weak rule — no parent larger than its child — and everything follows from how cheap that rule is to restore: one path, log n steps, on both insert and remove. The extreme is free to read. Use it whenever you need the best item repeatedly rather than all items in order: a size-k heap facing the wrong way for top-k, one heap per list for merging, two facing each other for a median, and one alongside a greedy rule for scheduling.