What is a binary heap data structure?
A binary heap is a heap-ordered tree data structure that supports efficiently finding the minimum or maximum element. It is commonly implemented as a complete binary tree stored in an array, making it suitable for priority queues, scheduling algorithms, and other selection problems.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Properties
A binary heap has two important properties:
-
Heap-order property: Every parent is less than or equal to its children in a min-heap, or greater than or equal to them in a max-heap.
-
Complete-tree property: Every level is completely filled except possibly the last, which fills from left to right.
For a zero-based array representation:
-
Parent of index
i:(i - 1) // 2 -
Left child of index
i:2 * i + 1 -
Right child of index
i:2 * i + 2
Because the tree is complete, the array has no gaps and avoids the memory overhead of explicit child pointers. Duplicate values are allowed, and the heap property does not imply that the remaining elements are globally sorted.
Operations and Complexity
The average-case figures below assume randomly ordered inputs.
| Operation | Best | Average | Worst | Auxiliary space | Reason |
|---|---|---|---|---|---|
| Peek at root | O(1) | O(1) | O(1) | O(1) | The root is stored at index 0 |
| Insert | O(1) | O(1) | O(log n) | O(1) iterative; O(log n) recursive | The element moves upward only until the heap property is restored |
| Remove root | O(1) | O(log n) | O(log n) | O(1) iterative; O(log n) recursive | The last element moves to the root and may sift downward |
| Build a heap | O(n) | O(n) | O(n) | O(1) iterative; O(log n) recursive | Bottom-up heapification processes all nodes |
| Find an arbitrary value | O(1) | O(n) | O(n) | O(1) iterative; O(n) recursive | Heap order does not preserve global ordering |
The heap itself uses O(n) total space, including its stored elements. Auxiliary-space figures exclude the input heap but include the recursion stack for recursive implementations.
Building a heap in O(n), rather than O(n log n), is possible because the number of nodes at height h above the leaves decreases geometrically while each node can sift down at most O(h) levels. Thus, the total work is bounded by a series equivalent to O(n × Σ(h / 2^h)), which converges to O(n).
Min-Heap vs. Max-Heap
| Heap type | Root contains | Typical use |
|---|---|---|
| Min-heap | Smallest element | Priority queues, Dijkstra’s algorithm with non-negative edge weights, event processing |
| Max-heap | Largest element | Scheduling, interval selection, streaming top-K calculations |
Python’s heapq module operates on a list as a min-heap. A max-heap can be simulated by negating numeric values or by storing (-priority, item) tuples. When priorities can tie and the item payloads should not determine the ordering, use a unique counter such as (-priority, counter, item).
Small Example
Consider the min-heap array [1, 5, 3, 8, 6]. Its root is 1; its children are 5 and 3; and 5 has children 8 and 6.
-
Insert
2, which is appended at index5. -
Its parent is at index
(5 - 1) // 2 = 2, containing3. -
Because
2 < 3, swap them, producing[1, 5, 2, 8, 6, 3]. -
Compare
2with its new parent at index0, containing1. -
Since
2 >= 1, stop. The resulting array satisfies the min-heap property.
Common Pitfalls
-
Confusing heap order with sorted order: Only the root is guaranteed to be the minimum or maximum.
-
Assuming
heapqis a max-heap: Negate values or use negative priorities for max-heap behavior. -
Using a nonexistent emptiness API:
heapq.isempty()is not available; useif not heaporlen(heap) == 0. Accessing or removing the root of an empty heap raisesIndexError. -
Ignoring ties: Add a counter before the item payload when equal priorities must not cause payload comparison or alter FIFO ordering.
-
Indexing errors: The root is index
0, and the child formulas are2 * i + 1and2 * i + 2. -
Unexpected mutation:
heapq.heapifyrearranges its list in place; copy the list first if the original ordering must be preserved. -
Edge cases: Empty heaps, one-element heaps, duplicates, and negative values should be handled explicitly where applicable.
-
Common follow-ups: Implement sift-up and sift-down, justify why heapify is O(n), and explain when to choose a heap instead of a sorted list.