--- title: "Heaps and Priority Queues: The Array That Is Secretly a Tree" description: "A binary heap drains 100,000 background jobs in 54.8 ms where a plain list with min() takes 72 seconds — a 1,300x gap from one rule: every parent is smaller than its children. Here is how the tree is never actually built, why sift up and sift down are the only two moves, why building bottom-up is O(n) and not O(n log n), and the four things a heap will not do for you." keywords: "binary heap, priority queue, heapq, sift up, sift down, heapify, data structures, algorithms, python heapq, heap vs sorted array, top k stream, job scheduler, dijkstra, big o, cs fundamentals, interview prep" created_at: "2026-08-13T09:00:00" post_type: "anonym_post" content_type: "technical_article" --- ![Banner](./banner.webp)

Prefer to watch? ▶ The full 15-minute episode ⚡ The 2-minute version ✈ Telegram

One warning before we start, because the word is overloaded. **This is the heap *data structure*, not the heap *memory region*** where your language allocates new objects. They share a name and nothing else — different concept, different field of study, zero overlap. If you came looking for the memory one (stack vs heap allocation), this is not that post, and it never touches it again. The data structure does exactly one job: **it always hands you the most urgent item next**, and it does that cheaply. --- ## Where this bites in real code You run background jobs — nightly reports, welcome emails, invoice files, password resets. For a long time you process them in arrival order, and that is fine. Then the queue gets long. One night there are **100,000 jobs waiting, and 12,000 of them are nightly reports**. A password reset lands at the back. Someone is sitting there, staring at a "check your email" screen, behind twelve thousand PDFs. The fix sounds trivial: stop taking the *oldest* job, take the *most urgent* one. That single change is the whole problem, because "find the smallest thing in a big pile, over and over" is startlingly expensive done naively. ### The two obvious implementations ```python # jobs.py — 100,000 queued jobs. always take the most urgent one next. jobs = [] # every job is a pair: (urgency, name) # way 1 — a plain list. cheap to add. expensive to choose. def take_most_urgent(jobs): best = min(jobs) # look at all 100,000 to find one jobs.remove(best) # then look at them all again to delete it return best # 72.0 seconds to drain the queue # way 2 — keep it sorted by -urgency, so the most urgent one is LAST. import bisect def add(jobs, urgency): bisect.insort(jobs, -urgency) # the search is fast. making room is not: # every item after that spot shifts by one. def take_sorted(jobs): return -jobs.pop() # free to take. 1.39 seconds for the queue. ``` Way 1 makes **two full passes over the list for every single job** you pull. Way 2 moves the cost to insertion: `bisect` finds the right slot in log n, but then every item after that slot shifts over by one, which is O(n) of memory movement. Measured on one machine, CPython 3.10, draining all 100,000 jobs:

Implementation	Time to drain 100,000 jobs	Cost per operation
Plain list + `min()`	72.0 s	O(n) to choose, O(n) to remove
Sorted list (`bisect.insort`)	1.39 s	O(n) to insert, O(1) to take
Binary heap	54.8 ms	O(log n) both ways

Seventy-two seconds. Not milliseconds — seconds, to work through a queue of background jobs. The sorted list is a real improvement and still spends **25x** what the heap does. The heap is roughly **1,300x** faster than the naive version. --- ## The bakery and the hospital Before any more code, one picture, because there is a confusion worth killing early. On the left, a **bakery**. You walk in, take a numbered ticket, and the counter calls the numbers in order. That is a plain FIFO queue. It never asks *why* you came. If you are in real trouble, you still wait behind everybody else. On the right, a **hospital**. The same five people walk in, in the same order. But a nurse at the desk asks one question each and reorders them on the spot. Arrival order stops mattering; urgency decides. A **priority queue** is that promise: items keep arriving, and whenever you ask, you get the best one out. It is a *behaviour*, not an implementation. A **binary heap** is the standard, cheap way to keep that promise — and it has only two moves in the entire structure: **sift up**, which runs when you add, and **sift down**, which runs when you take. --- ## The one rule Draw your items as a tree. Every circle holds one value. Now the rule, and there is only one: > **Every parent must be smaller than or equal to both of its children.** That is it. That is a heap. Read the rule again and notice what it does *not* say. It says **nothing about two nodes sitting next to each other**. `[3, 5, 7, 9, 12, 8, 14]` is a perfectly legal min-heap even though `12` sits before `8` — they are in different subtrees and the rule never compares them. This is the single most important thing to internalise: **a heap is not sorted**. `sorted([3, 5, 7, 9, 12, 8, 14])` gives you `[3, 5, 7, 8, 9, 12, 14]`, a different list. That weakness *is* the reason it is fast. Sorting maintains a global ordering on every insert; a heap maintains a local one, only along each parent-child edge, and a local promise is enormously cheaper to keep. --- ## There is no tree Here is the part that makes it cheap, and it is smaller than most people expect. There are no circles. There are no node objects. **There is a plain list.** Take the tree, read it level by level — top to bottom, left to right — and write those values into one flat array in that order. That array *is* the heap. The tree was only ever a picture we drew to explain it. Because the layout is fixed, family relationships become arithmetic: ```python # heap.py — the whole trick: the tree is never built. it is computed. def parent(i): return (i - 1) // 2 # who is above me def left(i): return 2 * i + 1 # my first child def right(i): return 2 * i + 2 # my second child # there is no Node class here. no left pointer, no right pointer, no # allocation per item. the tree is only a picture we draw of a flat list. def is_heap(heap): # the one rule the list must obey return all(heap[parent(i)] <= heap[i] for i in range(1, len(heap))) # $ python -i heap.py # >>> is_heap([3, 5, 7, 9, 12, 8, 14]) # True <- a legal heap # >>> sorted([3, 5, 7, 9, 12, 8, 14]) # [3, 5, 7, 8, 9, 12, 14] <- a different list. a heap is NOT sorted. ``` Three one-line functions replace an entire node class. To find who sits above index 7, you do not chase a pointer — you compute `(7 - 1) // 2 = 3`. No allocation per item, no pointer chasing, and the whole structure sits in one contiguous block of memory that the CPU cache actually likes. --- ## Move one: push, and sift up You add a job with urgency `2` — very urgent. It lands on the end of the list, at index 7, which is almost certainly the wrong place. So you fix it, one step at a time. The parent of index 7 is `(7-1)//2 = 3`, which holds `9`. Is `2 < 9`? Yes — trade places. Now your value sits at index 3, and you repeat against *its* parent. You climb until the rule holds again. ```python # heap.py — push: drop it on the end, then walk it up def sift_up(heap, i): while i > 0 and heap[i] < heap[parent(i)]: heap[i], heap[parent(i)] = heap[parent(i)], heap[i] # trade places i = parent(i) # and keep climbing def push(heap, item): heap.append(item) # the list just grows on the end sift_up(heap, len(heap) - 1) # at most one swap per level # the loop stops for one of two reasons: you reached index 0, or your # parent is already smaller than you. both mean the rule holds again. # $ python heap.py # before [3, 5, 7, 9, 12, 8, 14] # push(2) [2, 3, 7, 5, 12, 8, 14, 9] <- 3 swaps, 8 items ``` The loop stops for exactly one of two reasons: you reached index 0 (you are the smallest thing in the heap), or your parent is already smaller than you (the rule holds again everywhere above). --- ## Move two: pop, and sift down Taking the most urgent job out is the mirror image. **The answer itself is free** — it is always at index 0. The work is closing the hole. A heap has to stay a *complete* tree with no gaps, so you take the very last item in the list and drop it into the vacated root. It is almost certainly too big to be there, so you sink it: compare against both children, swap with the smaller of them, and repeat. ```python # heap.py — pop: the answer is index 0. the work is closing the hole. def sift_down(heap, i): n = len(heap) while True: smallest, l, r = i, left(i), right(i) if l < n and heap[l] < heap[smallest]: smallest = l if r < n and heap[r] < heap[smallest]: smallest = r if smallest == i: # nobody below me is smaller: stop return heap[i], heap[smallest] = heap[smallest], heap[i] i = smallest # follow the value down def pop(heap): last = heap.pop() # take the last item off the end if not heap: return last top = heap[0] # this is the answer we owe the caller heap[0] = last # drop the last item into the hole sift_down(heap, 0) # and sink it to where it belongs return top ``` The two length checks are not decoration. A node near the bottom may have one child or none, and reading `heap[left(i)]` without checking is an `IndexError` waiting for your production queue. ### Why both moves are cheap Both moves walk **one level at a time**, so the obvious question is: how many levels are there? A complete binary tree doubles at every level — 1 node, then 2, then 4, then 8. The number of levels is therefore log₂(n): how many times you can halve the count before reaching one. - 1,000,000 items → **19 levels** - 1,000,000,000 items → **29 levels** A thousand-fold increase in data costs you ten extra comparisons. That is the whole performance story. --- ## The move that surprises people: heapify Say you *already* have a list of a million jobs and you want a heap out of it. The obvious answer is to push them in one at a time. That is the wrong answer. Instead, start at the last node that actually has a child — halfway through the list — and walk **backwards** toward the root, sifting each node down. ```python # heap.py — you already HAVE the list. do not push it in one item at a time. def heapify(values): heap = list(values) start = len(heap) // 2 - 1 # the last node that HAS a child for i in range(start, -1, -1): # walk backwards, towards the root sift_down(heap, i) # everything below i is already legal return heap # the second half of any list is all leaves. a leaf has no children, so it # is already a legal heap of one item. that is why the loop skips them. ``` Why is this allowed? Because **the second half of any list is all leaves**, and a leaf has no children, so it is already a legal heap of one item. Half the work is free before you start. Measured, building a heap from 1,000,000 items on worst-case input:

Build strategy	Swaps	Swaps per item	Time
Bottom-up `heapify`	999,988	1.00	21.0 ms
Pushing one at a time	17,951,445	17.95	322.7 ms

One swap per item against eighteen — about **15x** on the clock. The reason is a counting argument, and it is the source of the classic "heapify is O(n), not O(n log n)" result: when you push one at a time, *every* item can climb the full height. When you build bottom-up, half the nodes are leaves and cannot sink at all, a quarter can sink one level, and only the single root can fall the full height. Sum nodes × distance across the tree and the series converges to n. --- ## The honest part: what a heap will not do This is where people get hurt. A heap answers **exactly one question**: what is the smallest thing you are holding. Everything else is a trap. - **It is not a sorted list**, and you cannot read it in order without emptying it. - **Finding a specific item by name means scanning the whole array** — precisely the O(n) cost you adopted a heap to avoid. - **There is no cheap delete-in-the-middle** and no cheap "change this job's priority" after it is queued. - **Even the second-smallest item is not simply at index 1.** It is at index 1 *or* index 2, and you must check both. Across 20,000 random heaps, it sat at index 2 in **8,074** of them. If you need any of those things, you need something *beside* the heap — typically a dictionary from job name to array position, maintained in step. Reaching for a heap and then searching through it is the mistake this section exists to prevent. --- ## Three guards before this ships ```python # scheduler.py — the three guards you need before this ships import heapq, itertools pq, counter = [], itertools.count() # 1. TIES. two jobs at urgency 5, so python compares the JOBS themselves: heapq.heappush(pq, (5, job)) # TypeError: Job vs Job heapq.heappush(pq, (5, next(counter), job)) # a counter never ties, so equal # urgency means first in, first out. # 2. YOU WANT THE LARGEST. negate the key. do not write a second heap. heapq.heappush(pq, (-score, next(counter), item)) # 3. TOP 10 OF A STREAM you cannot hold in memory. keep exactly 10. for value in stream: if len(top) < 10: heapq.heappush(top, value) elif value > top[0]: # top[0] is the worst of the best heapq.heapreplace(top, value) # one pop and one push, in one pass ``` 1. **Ties crash.** You push `(urgency, job)`. Two jobs at urgency 5 — Python compares the urgencies, finds them equal, then falls through to comparing the *job objects*. If your job class defines no ordering, that is a `TypeError` in production at 3 a.m. The fix is a monotonic counter in the middle: it can never tie, so equal urgency degrades gracefully to first-in-first-out. 2. **You often want the largest.** Negate the key on the way in and again on the way out. Do not maintain a second heap. 3. **Top-K of an unbounded stream.** Keep a heap of exactly K. Streaming 5,000,000 values for the top 10: sorting everything took **2,018 ms and held all 5M in memory**; the bounded heap took **1,078 ms and held 10**. Twice as fast and half a million times smaller. --- ## The AI angle: this is your inference scheduler If you serve models rather than web pages, you have not escaped this structure — you have just met it under different names. - **Continuous batching.** An LLM server holding hundreds of in-flight requests must decide, every iteration, which sequences join the next forward pass. That is a priority queue keyed on some mix of arrival time, sequence length and SLA class — and it is popped thousands of times per second, which is exactly the workload where 72 s versus 54.8 ms stops being academic. - **Deadline and preemption tracking.** Which request breaches its time-to-first-token budget soonest? That is `heap[0]`, in O(1). - **KV-cache eviction.** When GPU memory fills, something must be evicted — least-recently-used, lowest-priority, or furthest-from-completion. "What dies next" is the canonical heap question. - **Top-k sampling and beam search.** Selecting the k highest-probability tokens from a 100,000-entry vocabulary is a bounded-heap problem, guard 3 above, run once per generated token. - **Vector search.** Approximate-nearest-neighbour indexes (HNSW and friends) maintain candidate sets as bounded priority queues throughout the graph traversal. The lesson generalises: **when a system must repeatedly answer "which one next?" under pressure, a heap is nearly always underneath.** Recognising it is what lets you read a serving engine's scheduler and understand it in one pass. --- ## Where you have already used one You have almost certainly used a heap under a different name. Task schedulers use one to decide which job runs next. Timer systems use one to find the deadline expiring soonest. **Dijkstra's algorithm and A\***, the shortest-path algorithms behind map routing and game pathfinding, are a priority queue with a graph attached. And here is where you will write one yourself: top-K over a stream, cache expiry, retry queues. Anything at all where the words are *"handle the most important one first."* Python calls it `heapq`. Java calls it `PriorityQueue`. Go has `container/heap`. C++ has `priority_queue`. Same structure, same two moves. --- ## The verdict

Question	Answer
What is it?	A flat array obeying one rule: every parent ≤ both children.
What is it for?	Repeatedly answering "what is the most urgent item?" in O(log n).
Push / pop	O(log n) — one swap per level, 19 levels at a million items.
Peek the minimum	O(1) — it is index 0, always.
Build from an existing list	O(n) bottom-up, not O(n log n). 1.00 vs 17.95 swaps per item.
Find an arbitrary item	O(n). Do not do this. Keep a side index.
Read everything in order	O(n log n) and it destroys the heap. Use `sorted()`.
Reach for it when…	"Handle the most important one first" — schedulers, timers, top-K, Dijkstra, cache expiry.
Reach for something else when…	You need ordering, lookup by key, mid-queue deletion, or priority updates.

**The rule of thumb:** if you catch yourself calling `min()` inside a loop over a collection that keeps changing, you have hand-written the 72-second version. That is the moment to reach for `heapq`. --- ## Three interview questions If this comes up in an interview, these are the three that get asked — and all three answers come from one picture: **the tree above, and the same flat list below.** 1. **Why is a heap not just a sorted array?** Because a sorted array pays O(n) on every insert — everything after the new item shifts over. A heap only ever orders a parent against its own children, so it pays O(log n). 2. **Why is building a heap O(n) and not O(n log n)?** Because half the nodes are leaves and cannot sink at all, and only the root can fall the full height. Sum nodes × distance and the series converges to n. 3. **How do you get the largest instead of the smallest?** Negate the key, or wrap items in a class with reversed comparison. Never keep a second heap in sync with the first. --- Want the whole thing drawn, with sift up and sift down walked one swap at a time and every number above measured live? **[Watch the full episode on YouTube](https://youtu.be/xu7lnIBCKNg)** — or the [2-minute version](https://youtube.com/shorts/ILG1FQwqi4Q) if you just want the shape of it.