What Is a Heap? The Data Structure Behind Priority Queues
A heap is a tree-based structure that keeps the smallest or largest element at the root, enabling priority queues and heap sort in logarithmic time.
A heap is a tree-shaped data structure that keeps the smallest (or largest) element instantly accessible at the root, while still allowing new elements to be added and the root to be removed in logarithmic time. It’s the structure that makes priority queues practical, and it powers heap sort, shortest-path algorithms, and the “top-K” queries that show up constantly in production code.
The core idea: the heap property
Unlike a binary search tree, a heap doesn’t keep its elements in fully sorted order. It only enforces one rule, called the heap property:
- In a min-heap, every parent node is less than or equal to its children. The smallest element in the whole structure is always at the root.
- In a max-heap, every parent is greater than or equal to its children. The largest element sits at the root.
That’s it — there’s no guarantee about the relative order of siblings or of nodes at the same depth. This relaxed constraint is exactly what makes heaps fast: maintaining “root is smallest” is much cheaper than maintaining “everything is sorted.”
How a heap is stored
Conceptually a heap is a complete binary tree — every level is filled left to right before starting a new one. That completeness means a heap can be stored in a plain array with no pointers at all: for a node at index i, its children live at 2i + 1 and 2i + 2, and its parent lives at floor((i - 1) / 2). This is why heaps are so memory-efficient compared to pointer-based trees like a linked list or a search tree — you get tree behavior with array locality.
Insert and extract: sift up, sift down
Two operations do all the work:
- Insert. Append the new element at the end of the array (the next open leaf position), then “sift up”: repeatedly swap it with its parent as long as it violates the heap property. In the worst case this walks up the tree’s height, so insertion is
O(log n). - Extract the root. Save the root value, move the last element in the array into the root position, shrink the array, then “sift down”: repeatedly swap the new root with its smaller (or larger) child until the heap property holds again. Also
O(log n).
Peeking at the root — reading the minimum or maximum without removing it — is O(1), which is the whole reason heaps exist: cheap access to the extreme value, with cheap maintenance after every change. For background on what these complexity notations mean, see what Big O notation is.
Heap vs sorted array vs BST
| Operation | Sorted array | Balanced BST | Heap |
|---|---|---|---|
| Find min/max | O(1) | O(log n) | O(1) |
| Insert | O(n) | O(log n) | O(log n) |
| Extract min/max | O(n) | O(log n) | O(log n) |
| Build from n items | O(n log n) | O(n log n) | O(n) |
| Arbitrary lookup | O(log n) | O(log n) | O(n) |
The last row is the tradeoff to remember: a heap is excellent at “give me the extreme value” and terrible at “does this specific value exist.” If you need both fast extremes and fast arbitrary search, you likely want a BST or a hash table alongside it, not a heap alone.
Where heaps actually get used
Priority queues. A heap is the standard implementation of a priority queue, where each element carries a priority and you always want to process the highest (or lowest) priority item next — task schedulers, event simulations, and shortest-path search all lean on this.
Heap sort. Building a max-heap from an array and repeatedly extracting the max gives a comparison-based sort that runs in O(n log n) time with O(1) extra space — no recursion stack like quicksort, no auxiliary array like merge sort.
Top-K problems. Need the 10 largest values out of a stream of a million? Keep a min-heap of size 10: push each new value in, and if the heap exceeds size 10, pop the smallest. You never hold more than 10 elements at once, and you never need to sort the whole stream.
Median maintenance. Two heaps — a max-heap for the lower half of the data and a min-heap for the upper half — let you track a running median in O(log n) per insertion, which is far cheaper than re-sorting on every new value. This kind of incremental problem-solving shows up often in dynamic programming as well, where the goal is similarly to avoid redoing work you’ve already paid for.
Binary heaps vs other heap variants
The array-backed binary heap described above is the version you’ll meet in almost every standard library. Variants like Fibonacci heaps and pairing heaps offer better amortized bounds for certain operations — notably a cheap “decrease-key” operation that matters for graph algorithms on very large graphs — but they carry higher constant-factor overhead and more complex implementations. For most applications, a plain binary heap is the right default; reach for the exotic variants only when profiling shows decrease-key is actually the bottleneck.
The takeaway
A heap trades full ordering for a cheaper guarantee: the root is always the smallest (or largest) element, insert and extract both run in O(log n), and the whole structure fits in a flat array thanks to its complete-binary-tree shape. That’s enough to power priority queues, heap sort, and top-K queries without ever needing to fully sort the data — reach for one whenever “give me the next most urgent item” matters more than “keep everything in order.”
Keep reading
The Lycoris Team · · 4 min read The KMP Algorithm: Fast String Matching Explained
The Knuth-Morris-Pratt algorithm finds a pattern inside a text in linear time by never re-examining characters it has already matched.
The Lycoris Team · · 5 min read What Is a Ring Buffer?
A ring buffer is a fixed-size array that wraps its read and write pointers around, giving O(1) enqueue and dequeue without ever resizing.
The Lycoris Team · · 5 min read Fenwick Trees (Binary Indexed Trees), Explained
A Fenwick tree, or binary indexed tree, answers prefix-sum queries and point updates in O(log n) with far less memory than a segment tree.