⛰️ Binary Heap
Priority queue as an array
Setup
Stats
Heap size
0
Comparisons
0
Swaps
0
Last op
Ready
Info & Theory

A binary min-heap is a complete binary tree — every level fully filled except possibly the last, which fills left to right — that maintains the invariant that every parent is less than or equal to both of its children.

Array representation

Because the tree is always complete, it needs no pointers. For a node stored at index i, its parent lives at ⌊(i−1)/2⌋ and its children at 2i+1 and 2i+2. The tree shape is entirely implicit in the indexing.

Sift-up (insert)

A new value is appended at the end of the array, then compared with its parent and swapped upward while it is smaller, until the heap property holds or it reaches the root. This follows one root-to-leaf path, so it costs O(log n).

Sift-down (extract-min)

Removing the minimum swaps the root with the last element, shrinks the array by one, then repeatedly swaps the new root with its smaller child until the heap property holds. Also O(log n).

Floyd's build-heap in O(n)

Calling sift-down on every internal node from ⌊n/2⌋−1 down to 0 builds a heap from n arbitrary values. Although this looks like O(n log n), most nodes sit near the bottom of the tree where sift-down travels only a short distance; the total work summed across all levels is a converging series that adds up to O(n).

Applications

Binary heaps implement priority queues efficiently, power heapsort (an in-place O(n log n) sort), and back the frontier of Dijkstra's and Prim's algorithms, where the next-cheapest item must repeatedly be found and removed.

About Binary Heap — Priority Queue

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 11 July 2026

A binary heap is a complete binary tree — every level fully filled except possibly the last, filled left to right — stored compactly in a plain array with no pointers. For any index i, its parent lives at ⌊(i−1)/2⌋ and its children at 2i+1 and 2i+2, so the tree structure is implicit in the indexing scheme alone. A min-heap maintains the heap property: every parent's value is less than or equal to both of its children, guaranteeing the smallest element always sits at index 0, though the array itself is not fully sorted. Inserting a value appends it at the end and sifts it upward, swapping with its parent while the heap property is violated — an O(log n) operation bounded by the tree's height. Removing the minimum swaps the root with the last element, shrinks the array, then sifts the new root downward toward its smaller child, again O(log n). Building a heap from n unsorted values by sifting down from the last internal node runs in O(n) total, not O(n log n), because most nodes sit near the bottom, where sift-down does little work. Binary heaps underlie priority queues, heapsort, and Dijkstra's and Prim's algorithms.

Frequently Asked Questions

Why can a binary heap be stored in an array without pointers?

Because it is a complete binary tree, filled level by level with no gaps, a node's parent and children can be computed directly from its array index (parent = ⌊(i−1)/2⌋, children = 2i+1 and 2i+2). This avoids the memory overhead of pointer-based tree nodes and gives excellent cache locality compared with linked structures.

What is the time complexity difference between sift-up and sift-down?

Both run in O(log n) in the worst case, since each follows only a single root-to-leaf path of length ⌊log₂ n⌋. Sift-up makes at most one comparison per level against the parent, while sift-down makes up to two comparisons per level against both children, so sift-down has a slightly larger constant factor despite sharing the same asymptotic bound.

Why is building a heap from n elements O(n) rather than O(n log n)?

Floyd's build-heap algorithm calls sift-down only on internal nodes, starting from the last one and working up to the root. Most nodes are near the bottom of the tree, where a sift-down can travel only a short distance; summing the work across all levels gives a geometric series that converges to O(n), unlike the O(n log n) cost of inserting n elements one at a time.

What is the difference between a min-heap and a max-heap, and how does a heap compare to a balanced BST for a priority queue?

A min-heap keeps the smallest value at the root (parent ≤ children); a max-heap keeps the largest (parent ≥ children) — the same algorithms apply with the comparison flipped. Compared with a balanced binary search tree, a heap gives the same O(log n) insert and O(log n) extract-min, but with a simpler array-based implementation, no rebalancing logic, and O(1) peek at the minimum, whereas a BST offers ordered traversal and O(log n) search for arbitrary keys that a heap does not support.