Heaps and Priority Queues: How a Binary Heap Works
A binary heap stores a priority queue in an array, keeping the smallest item at the top, so each insert and each removal takes logarithmic time, or O(log n).
A heap is a tree-shaped structure in which each parent is ordered relative to its children, and a priority queue is an abstract data type that always returns the most urgent item first. The standard way to build a priority queue is a binary heap. In a min-heap, the smallest value sits at the root, and inserting or removing items takes O(log n) time, where n is the number of items. This is not the memory heap a program uses for allocation, although the name is shared.
What are the parts of a binary heap?
A binary heap follows two rules. The shape rule says the tree must be complete: every level is full except possibly the last, which fills from left to right. The order rule says that in a min-heap, every parent is less than or equal to its children. The shape rule is what makes the structure cheap to store. Nodes live in a plain array with no pointers. The node at index i has children at 2i + 1 and 2i + 2, and its parent sits at index (i − 1) divided by 2, rounded down.
The order rule is weaker than full sorting. The two subtrees under a node have no required order between them, which is why a heap is much cheaper to keep correct than a sorted list.
How do insert and remove move items?
| Operation | What moves | Typical cost |
|---|---|---|
| Peek at the minimum | Nothing; the root is read | O(1) |
| Insert | New item goes to the end, then rises | O(log n) |
| Remove the minimum | Last item moves to the root, then sinks | O(log n) |
Insertion appends the new value to the next free slot. If it is smaller than its parent, the two swap, and the value keeps rising until its parent is smaller or it reaches the root. Removal takes the root out, moves the last array element into its place to keep the shape rule, and then sinks that element. At each step it swaps with the smaller of its two children whenever it is larger than that child.
Take a min-heap whose array holds 5, 9, 7, 12, 10 and 8, in that order. Inserting 2 places it at index 6, below the 7. Since 2 is smaller than 7, the two swap. The 2 is then compared with its new parent, the root 5, swaps again, and stops at the top. The array now holds 2, 9, 5, 12, 10, 8 and 7, and every parent is still less than or equal to its children.
Only one value travels, along a single path from a leaf to the root or from the root to a leaf. The rest of the tree stays still. The motion is local, but the result is global: the order rule holds everywhere. A complete tree with n items has a height of about log₂ n, so no value moves more than about that many steps. This is why the cost stays logarithmic even for millions of items.
Why are priority queues useful?
Priority queues appear wherever the next most important item must come out first. Dijkstra's shortest path algorithm repeatedly removes the closest unvisited node from a priority queue. Event simulators process events in time order, and operating systems use similar queues to choose which task runs next. Heapsort uses the same structure to sort. It builds a heap, then removes the minimum repeatedly, in O(n log n) time and without extra memory beyond the array.
When is a heap the wrong choice?
A heap is good at finding the smallest item but poor at finding an arbitrary value, which takes O(n) time because the rest of the data is not in sorted order. If you need quick lookups by key, a hash table is usually the better fit. If the data is already sorted, binary search is faster. Heaps also do not let you read the values in order without removing them one at a time, so they are a poor choice for printing a full sorted list.
Speed claims like these are measured in Big O notation, which describes how the cost grows with the size of the input.
Tags
algorithms complexity data structures priority queue
Related articles
- Hash Tables
- Dijkstra's Shortest Path Algorithm
- Binary Search
- Big O Notation
- The Traveling Salesman Problem: Why the Shortest Route Is Hard
- Big-Endian vs Little-Endian: Byte Order Explained