A binary heap is a data structure organized as a complete binary tree in which each parent’s key is ordered relative to its children. In a min-heap, every parent’s key is no greater than its children’s keys; in a max-heap, it is no smaller. Consequently, the root contains a minimum or maximum key, respectively. Binary heaps are commonly stored in arrays and are widely used to implement priority queues and the heapsort algorithm.
Structure and ordering
A binary heap satisfies two independent conditions:
- Shape property: Every level is full except possibly the lowest, which is filled from left to right.
- Heap-order property: Each parent precedes or ties its children under the chosen priority ordering.
For a min-heap with key function , the ordering condition is
for every non-root node . A max-heap reverses the inequality. Duplicate keys are permitted.
The shape property ensures that a nonempty heap containing elements has height
when height is measured in edges. This logarithmic height bounds the number of levels traversed during insertion and removal.
Heap order is only a partial ordering of the elements. It constrains ancestors and descendants but does not generally order siblings or elements in separate subtrees. For example, the array
[2, 5, 3, 9, 7, 8, 4]
represents a valid min-heap even though the array is not sorted.
A binary heap is therefore different from a binary search tree. A search tree orders keys across its left and right subtrees to support search; a heap makes an extreme key immediately available without maintaining enough order for efficient arbitrary-key lookup.
Array representation
A binary heap is usually represented by an array rather than by individually allocated nodes with pointers. Completeness allows the tree’s relationships to be recovered directly from array positions.
For zero-based indexing, a node at index has:
A child exists only if its index is less than the current heap size . With one-based indexing, the corresponding indices are , , and .
This representation requires no explicit links between nodes and stores the heap in level order. It has low per-element overhead and generally favorable spatial locality, although root-to-leaf paths can still span multiple cache lines in large heaps.
The heap’s logical size must be distinguished from its array capacity. Slots beyond the logical size are not part of the heap.
Fundamental operations
The following descriptions use a min-heap. Max-heap operations reverse the comparisons.
Inspecting the minimum
The minimum is stored at the root, so inspecting it takes time. The operation is undefined for an empty heap unless the interface specifies an error, sentinel, or optional result.
Insertion and sift-up
Insertion first appends an element at the next available position, preserving completeness. The element is then compared with its parent. If its key is smaller, it is exchanged with the parent, and the process continues upward.
This operation is called sift-up, bubble-up, or percolate-up. Only the newly introduced ancestor path can violate heap order, so repairing that path restores the invariant.
Insertion requires heap work in the worst case. If the backing array must grow, an individual insertion may additionally require copying or movement. With geometric capacity growth, the array-growth contribution is amortized per insertion.
Removing the minimum and sift-down
To remove the root:
- Save the root element.
- Move the last element into the root position and reduce the heap size.
- Compare the replacement with its children.
- If it is greater than the smaller child, exchange them and continue downward.
This repair operation is called sift-down, bubble-down, or percolate-down. Choosing the smaller child is essential: moving the larger child upward could leave it greater than its sibling.
Removal takes time in the worst case. A one-element heap simply becomes empty.
The following pseudocode performs sift-down in a zero-indexed min-heap, assuming that the child subtrees already satisfy heap order:
sift_down(A, i, n):
while 2*i + 1 < n:
child = 2*i + 1
right = child + 1
if right < n and A[right] < A[child]:
child = right
if A[i] <= A[child]:
break
swap A[i], A[child]
i = child
Implementations may move elements through a temporary “hole” rather than repeatedly swapping them, reducing assignments while preserving the same asymptotic bound.
Changing priorities and deleting known elements
If an element’s position is known, decreasing its key in a min-heap may require sift-up; increasing its key may require sift-down. Either operation takes time.
An arbitrary element at a known position can be deleted by replacing it with the last element and repairing upward or downward as appropriate. This also takes .
The qualification “position is known” matters. Searching for a particular value in an ordinary binary heap takes time in the worst case. An indexed priority queue maintains an additional mapping from element identifiers to heap positions, often using an array or hash table. Every movement within the heap must update that mapping.
Building a heap
A heap can be built by repeatedly inserting elements, which takes time in the worst case. A more efficient method constructs it bottom-up.
For a zero-indexed array of length , all positions from onward are leaves and already satisfy heap order individually. Starting at the last internal node, , the algorithm applies sift-down at each position in reverse order until it reaches the root.
This procedure, commonly called bottom-up heap construction or build-heap, takes time. It is often associated with Robert W. Floyd’s work on heapsort.
The linear bound follows because most nodes are near the leaves and can move only a short distance. An upper bound on the total work is proportional to
Although one sift-down can cost , only a small fraction of nodes have that much height available. Multiplying the maximum sift-down cost by every node therefore gives a loose bound.
The term heapify is ambiguous: some interfaces use it for building an entire heap, while some algorithm descriptions use it for a single sift-down operation.
Complexity
Under the usual model of constant-time key comparison and element movement, the main time complexities are:
| Operation | Time bound |
|---|---|
| Inspect minimum or maximum | |
| Insert, excluding array reallocation | worst case |
| Remove minimum or maximum | worst case |
| Change key at a known position | worst case |
| Delete at a known position | worst case |
| Search for an arbitrary key | worst case |
| Bottom-up construction | |
| Merge two heaps by concatenation and rebuilding |
Storage for elements is . Iterative sift-up and sift-down use auxiliary space. Recursive implementations may instead use call-stack space.
These bounds exclude costs intrinsic to the stored objects. Comparing long strings or moving large records can make a nominally constant-time step more expensive.
Applications
Priority queues
A priority queue is an abstract data type specifying operations such as insertion and removal of the highest-priority item; a binary heap is one concrete implementation.
Heap-based priority queues support event simulation, task selection, and scheduling systems in which the next item is determined by priority rather than arrival order.
They are also used in graph algorithms. Dijkstra’s algorithm can use a min-heap to select the next vertex with the smallest tentative distance, while A* search orders candidates by estimated total path cost. Implementations may support direct priority updates or insert revised entries and ignore obsolete entries when removed.
Heapsort
Heapsort builds a max-heap, repeatedly exchanges the root with the last element in the active heap, and restores heap order after shrinking the active region. This produces an ascending sequence.
The method is a sorting algorithm with worst-case running time. Its conventional iterative implementation uses auxiliary space, but it is not stable: equal-key elements may change their relative order.
Selection and merging
A heap of size can retain the largest elements encountered in a stream. A min-heap exposes the smallest retained element, making it easy to decide whether a new element should replace it. Processing elements takes time for and storage.
For merging sorted sequences, a min-heap can hold the next available element from each sequence. After extracting the smallest, the algorithm inserts its successor from the same sequence. For total elements and , this gives time.
Limitations and implementation considerations
No efficient general search. Heap order is insufficient for binary search within the backing array. Ordered traversal and range queries are usually better supported by search trees.
No inherent stability. Equal-priority elements need not be removed in insertion order. A stable priority queue can compare a pair consisting of the priority and an insertion sequence number.
Mutable keys require repair. Changing a key externally without restoring heap order can invalidate subsequent operations. Interfaces may prohibit such mutation or require explicit update operations.
Comparison rules must be consistent. Correctness depends on a coherent ordering relation. Values such as floating-point NaN need explicit treatment when the language’s ordinary comparisons do not provide the required ordering.
Merging is not especially efficient. Concatenating two heap arrays and rebuilding takes linear time in their combined size. This is useful for bulk merging but does not provide the efficient meld operations available in some other heap structures.
Array positions are not stable identities. Insertions, removals, and repairs move elements. External references to positions require maintenance, and array reallocation may also invalidate direct memory references.
History and related structures
J. W. J. Williams introduced the binary heap in connection with heapsort in 1964. Floyd published an improved heapsort method in the same year, including the bottom-up construction technique that underlies standard linear-time build-heap procedures.
A binary heap is a special case of a d-ary heap, in which each node can have up to children. Larger branching factors reduce tree height but require examining more children during sift-down.
Other priority-queue structures make different trade-offs. Binomial heaps support efficient merging, while Fibonacci heaps provide stronger amortized bounds for operations such as decrease-key. Binary heaps remain widely used because their array representation is compact, their algorithms are simple, and their practical overhead is relatively low.
The word heap also denotes a region used for dynamic memory allocation. That use is distinct from the binary-heap data structure; a memory allocator need not organize its storage as a binary heap.