Card 07/ 09
Heap vs Sorted Array for a Priority Queue
A heap gives up full order to make every insert O(log n).
A binary heap and a sorted array can both serve as a priority queue, a collection that always hands back its smallest item next, but they spend their effort in different places. This card covers what each costs, operation by operation, and which workloads favour which.
A binary min-heap is a complete tree stored in an array, in which every parent is no larger than its children; only the smallest item has a known position. A sorted array keeps every item in order. To make removing the smallest item cheap, keep the array sorted largest first, so the smallest item sits at the end and can be removed without shifting anything. The table compares the two for n items.
| Operation | Binary heap | Sorted array, largest first |
|---|---|---|
| Read the smallest item | O(1), at index 0 | O(1), at the end |
| Remove the smallest item | O(log n), one sift-down | O(1), from the end |
| Insert an item | O(log n), one sift-up | O(n): binary search finds the place in O(log n), then the smaller items shift along |
| Build from n items | O(n), bottom-up | O(n log n), a sort |
| Visit every item in order | O(n log n), by popping each one | O(n), a walk along the array |
| Find the k-th smallest item | O(k log n), k pops | O(1), by index |
The heap wins wherever inserts and removals interleave. A scheduler that receives n jobs and runs n jobs makes 2n operations; the heap does them in O(n log n) in total, while the sorted array pays O(n) for each insert and O(n²) overall. The heap gets this by keeping less order: it never decides how two items on different branches compare, so an insert repairs one path instead of shifting half the array.
The sorted array wins when the items are mostly fixed and read in order. A list of exam results loaded once and then read from top to bottom, or queried for the tenth best result, needs one sort and then answers everything by position.
A rule of thumb: if the code would call sort again after each insert, it wants a heap; if it sorts once and then only reads, it wants the sorted array. Both use the same memory, one slot per item, and both keep their items in one contiguous array.
← → move through sections and cards