In data structures, a heap is a tree-based structure that satisfies the heap property: every parent node is ordered relative to its children, so the smallest or largest element always sits at the root. A min-heap keeps the smallest key on top, and a max-heap keeps the largest. The most common form, the binary heap, is a complete binary tree stored compactly in an array.
Heaps are the standard implementation of a priority queue, offering constant-time access to the top element and logarithmic-time insertion and removal. The heap data structure is unrelated to the heap memory region used for dynamic allocation; the two only share a name.
How a binary heap is organized
A binary heap combines two rules. The shape property requires a complete binary tree: every level is full except possibly the last, which fills from left to right. The heap property requires that each parent is less than or equal to its children in a min-heap, or greater than or equal in a max-heap.
Because the tree is complete, it needs no pointers. Nodes are stored level by level in an array, and simple index arithmetic finds relatives. With zero-based indexing, the children of index i are at 2i + 1 and 2i + 2, and its parent is at (i – 1) / 2 rounded down. This layout is compact and cache-friendly.
The heap property orders only parents and children, not siblings or separate subtrees. A heap is therefore partially ordered: it always knows its minimum or maximum, but reading the array from left to right does not give sorted output.
Core heap operations and their cost
Heap operations restore the heap property by moving one element up or down a single path of the tree, which has a length of about log2 n for n elements. That path length is the source of the logarithmic costs below.
| Operation | How it works | Time complexity |
|---|---|---|
| Peek | Read the root element | O(1) |
| Insert (push) | Append at the end, then sift up | O(log n) |
| Extract top (pop) | Move last element to root, then sift down | O(log n) |
| Decrease or increase key | Change a key, then sift up or down | O(log n) with a known position |
| Build heap from n items | Sift down from the last parent to the root | O(n) |
| Search for arbitrary value | Scan the array | O(n) |
The linear-time build surprises many developers. Inserting n items one by one costs O(n log n), but bottom-up heapify costs only O(n), because most nodes sit near the leaves and need very short sift-down paths.
Heap variants and when they matter
The binary heap is the default, but several heap variants trade simplicity for faster specific operations, especially merging two heaps or decreasing keys. These matter mainly in graph algorithms and specialized schedulers.
| Variant | Key strength | Main drawback |
|---|---|---|
| Binary heap | Simple, array-based, fast in practice | Merging costs O(n) |
| d-ary heap | Shallower tree, cheaper sift-up | More comparisons per sift-down |
| Binomial heap | Merge in O(log n) | More complex pointer structure |
| Fibonacci heap | Amortized O(1) insert and decrease-key | High constant factors, complex code |
| Pairing heap | Simple and fast in many benchmarks | Harder worst-case analysis |
Theoretical advantages do not always translate into speed. The Fibonacci heap improves the asymptotic bound of Dijkstra’s shortest-path algorithm, yet a binary or 4-ary heap often runs faster on real hardware because of better memory locality.
Heap compared with related data structures
A heap is often confused with the priority queue and with the binary search tree. The priority queue is the abstract interface, while the heap is one concrete implementation; a binary search tree maintains a full sorted order rather than only a top element.
| Structure | Ordering kept | Find minimum | Best suited for |
|---|---|---|---|
| Binary heap | Parent versus children only | O(1) | Repeatedly taking the top priority item |
| Balanced binary search tree | Full sorted order | O(log n) | Range queries and ordered iteration |
| Sorted array | Full sorted order | O(1) | Static data with rare inserts |
| Unsorted array | None | O(n) | Very small collections |
| Hash table | None | O(n) | Lookup by key, not by priority |
The choice usually comes down to which questions the program asks most often. If it only needs the next item by priority, a heap is simpler and faster than a search tree. If it also needs to list items in order, find values within a range or delete arbitrary entries efficiently, a balanced search tree or an indexed priority queue that tracks each element’s position is the better fit.
Practical uses and implementation pitfalls
Heaps appear wherever a program must repeatedly select the next most important item. Standard libraries provide them directly, for example as a priority queue class or as heap functions over an array.
- Heapsort sorts in O(n log n) time with O(1) extra memory, although it is usually slower than quicksort in practice.
- Dijkstra’s and Prim’s algorithms use a min-heap to choose the closest unvisited node.
- Task and event schedulers keep pending jobs ordered by deadline or priority.
- Top-k problems keep a min-heap of size k to track the k largest values in a stream.
- K-way merging of sorted files uses a heap holding the current head of each file.
Common implementation mistakes include off-by-one errors in parent and child index formulas, forgetting to sift after changing a key, and assuming a library heap is a max-heap when it is a min-heap, or the reverse. Library heaps also rarely support efficient removal of arbitrary elements, so many programs use lazy deletion, marking stale entries and skipping them when they reach the top.
Explained without jargon
A heap is a way of storing items so that the most urgent one is always on top. Think of a hospital emergency room. Patients do not wait in arrival order. The most serious case is always seen next.
The heap does not keep everything perfectly sorted, which would be slow. It only makes sure the top item is correct. When that item leaves, the heap quickly rearranges a few items so the next most urgent one moves up.
A typical use case
A navigation service computes driving routes on a road graph with millions of intersections using Dijkstra’s algorithm. Each step needs the unvisited intersection with the smallest known travel time, so the implementation keeps candidates in a binary min-heap keyed by travel time.
Scanning all candidates at every step would take time proportional to their number. With the heap, each extraction and update costs only logarithmic time, and stale entries are skipped through lazy deletion. Combined with other optimizations, this lets the service answer route requests in a fraction of a second instead of making users wait.