Why do most priority queues use a binary heap rather than a sorted list or a balanced search tree?
answer
- What does the contract actually ask about
- Sorted structures maintain more order than needed
- Where does a sorted list spend its time
- Parent outranks children, siblings unordered
- Contiguous array, index arithmetic, no pointers
basics
~20 sA binary heap does exactly what the priority queue contract asks and no more: it keeps only a partial order, so insert and extract cost O(log n) and peek O(1). Sorted lists pay O(n) per insert; search trees pay pointer and cache overhead for ordering nobody asked for.
solid answer
~50 sThe contract only ever asks about the top element, and a binary heap maintains only the ordering needed for that: every parent outranks its children, with no relationship between siblings. Maintaining a *total* order — which is what a sorted list or a balanced search tree does — is strictly more work than the contract requires. Concretely: sorted array or list gives O(1) peek and extract but O(n) insert, because everything after the insertion point shifts or has to be walked to. A balanced search tree gives O(log n) everywhere but stores two or three pointers per node, scatters those nodes across memory, and needs rebalancing code. The heap lives in one contiguous array, addresses children by index arithmetic, needs no pointers, is cache-friendly, and bulk-builds from n items in O(n). You give up ordered traversal and cheap arbitrary search — neither of which the abstraction promised.
go deeper
Recall the headline costs of a heap-backed priority queue: peek O(1), insert and extract O(log n). Be able to say why a sorted list is worse when items keep arriving.
Explain the partial-order invariant — parent outranks children, siblings unrelated — and why maintaining less order is cheaper than maintaining a full sort. Name the array layout with index arithmetic instead of pointers.
Bring in the constants: pointer overhead, cache locality, bulk building in linear time, and the cases where a tiny bounded queue or a build-once-drain-once workload makes the simpler structure the right call.
Own the call when the same data must also be listed, ranged over, or cancelled. That is usually a second index or a different structure entirely, and deciding which cost the team carries is the actual decision.
## The contract asks for very little A priority queue is only ever asked about its top element. That is the key observation: any structure that keeps *more* order than "who is on top" is doing unpaid work. A binary heap maintains exactly one invariant — **every parent outranks both of its children** — and nothing else. Siblings are unordered relative to each other; a node three levels down may outrank a node one level down in a different subtree. This is a **partial order**, and it is much cheaper to maintain than a total order. ## The cost table Take a support desk that inserts tickets as they arrive and pulls the most urgent one whenever an agent frees up, so inserts and extractions interleave constantly. | Backing structure | insert | peek | extract-top | bulk build | notes | |---|---|---|---|---|---| | Unsorted array | O(1) | O(n) | O(n) | O(1) | cheap in, expensive out | | Sorted array | O(n) | O(1) | O(1) | O(n log n) | shifting dominates inserts | | Sorted linked list | O(n) | O(1) | O(1) | O(n log n) | no shifting, but O(n) scan to place | | Balanced search tree | O(log n) | O(log n), O(1) cached | O(log n) | O(n) from sorted input | full ordering, pointer overhead | | Binary heap | O(log n) | O(1) | O(log n) | O(n) | partial order only | The unsorted array and the sorted array are the two extremes: one pushes all the cost to insertion, the other to extraction. Under an interleaved workload both are O(n) per operation on average, which is the thing the heap escapes. The heap sits in the middle — O(log n) both ways — and is the balanced answer for a workload with no idea which operation dominates. ## Why not the balanced search tree, since everything is O(log n)? Asymptotically the tree matches the heap and even beats it on peek if you cache a pointer to the leftmost node. In practice it loses on constants: - **Memory per element.** A tree node carries two child pointers, often a parent pointer, and balance metadata. The heap stores the elements in a plain array and derives the children of index `i` arithmetically — for a zero-based array, `2i+1` and `2i+2`. Zero bytes of structural overhead. - **Locality.** Heap sift paths walk array slots that are near each other at the top of the tree, so the hot upper levels stay resident in cache. Tree nodes are separately allocated and land wherever memory happened to be free, so each level down is a likely cache miss. - **Code and bug surface.** Rebalancing (rotations, colour or height bookkeeping) is far more code than sift-up and sift-down, which are a dozen lines each. - **Bulk loading.** Turning n arbitrary items into a heap bottom-up is O(n), better than the O(n log n) of inserting them one at a time. You pay for that with capabilities the contract never asked for: the tree can list everything in order, find neighbours of a key, and delete an arbitrary element in O(log n). In a heap, ordered listing does not exist and finding an arbitrary element is an O(n) scan. ## Big-O is not the whole argument, and the alternatives sometimes win The asymptotics say nothing at small n, and constants decide there. Cases where the "worse" structure is the right call: - **Tiny queues.** Ten pending items, and a linear scan over a flat array beats every log factor while being trivially readable. If the queue is bounded small by construction, say so and take the simple thing. - **Build once, drain once.** If every insert happens before any extraction, sort the batch once and walk it. You get the same asymptotics, less machinery, and a browsable ordered list as a side effect. - **You actually need ordering.** If the same data must also be listed in order, or scanned by range, the search tree pays for itself and you read the top off it. - **You need cheap cancellation.** Arbitrary removal is O(n) in a heap. If cancellations are frequent, either keep a separate index or use a structure that supports removal directly. ## The interview answer in one line The heap wins the default because the priority queue contract characterizes only the top, the heap maintains only the ordering that characterizes the top, and it does so in a contiguous array with no pointers. State the invariant, state what it gives up, and name one workload where you would not choose it.
- When would you pick a plain sorted array over a heap-backed priority queue?Two cases. When the queue is bounded small — a handful of pending items, where a linear scan beats every log factor and reads better. And when all insertions happen before any extraction: sort the batch once, walk it, and you also get a listing you can show a user. The heap earns its keep only when inserts and extractions interleave.
- What does a heap-backed queue give up compared with a balanced search tree?Ordered traversal of the contents, neighbour queries around a key, and cheap arbitrary lookup or removal — all of which are O(log n) in a tree and O(n) or nonexistent in a heap. It buys back constant-factor speed, zero pointer overhead, better cache behaviour and much less code. You trade capability you were not promised for speed on the capability you were.
saying these in an interview costs you the question
- Says a heap keeps its elements sorted
- Claims heap insert is O(1)
- Picks a sorted list for O(1) peek, ignoring O(n) inserts
- Argues a balanced tree is strictly better because everything is O(log n)
- Thinks locating an arbitrary element in a heap is O(log n)
- Treats asymptotics as decisive at n of ten