Binary heap visualizer

The heap starts as a min-heap built from ten values. Type a number and press Insert, or press Extract min to remove the root. Every operation plays step by step: the highlighted nodes are the ones being compared or swapped, and the sentence under the controls says what happened and why. Use Back, Next and Play to move through the steps, and switch to a max-heap to see the same rules with the order reversed.

• Build from random array runs Floyd’s bottom-up build-heap on twelve random values; compare its comparison count with inserting the same values one by one.
• Heapsort sorts a copy of the heap in place; watch the sorted part grow at the end of the array.
• Insert a value smaller than every other in a min-heap and count the swaps: it climbs all the way to the root.

The operations follow the textbook algorithms. Inserts produce exactly the same array as Python’s heapq.heappush, and extracting everything returns the values in the same order as heapq.heappop; both were checked on 200 random inputs, for min-heaps and max-heaps.

A binary heap is a binary tree with two rules. Its shape is complete: every level is full except possibly the last, which fills from left to right. And it has the heap property: in a min-heap every parent is less than or equal to its children, so the smallest value is at the root; in a max-heap every parent is greater than or equal to its children.

Nothing is said about the order of siblings or of different branches, which is what makes a heap cheap to maintain. It cannot find an arbitrary value quickly or list values in order, but it always knows the minimum (or maximum), and it can add a value or remove the top in time proportional to the tree’s height. That is exactly what a priority queue needs.

J. W. J. Williams introduced the binary heap in 1964 as the data structure behind heapsort, and Robert Floyd published the linear-time way to build one the same year.

Because a complete tree has no gaps, its nodes can be numbered level by level, left to right, and stored in that order in an array. With indexes starting at 0, the node at index i has its children at 2i + 1 and 2i + 2 and its parent at ⌊(i − 1) / 2⌋. No pointers are stored, the array is contiguous in memory, and adding a node at the bottom of the tree is just appending to the array. (Some textbooks start indexes at 1, giving children 2i and 2i + 1 and parent ⌊i / 2⌋.)

The simulator draws both views of the same data: the tree, and below it the array with each node’s index. A tree with n nodes has ⌊log₂ n⌋ levels below the root, so a heap of a million elements is only 19 levels deep.

To insert, put the new value in the next free slot, the end of the array, which keeps the tree complete. The only place the heap property can now fail is between the new value and its parent. If the new value belongs above its parent (it is smaller, in a min-heap), swap them and repeat from the parent’s position. Stop when the parent is in order or the value reaches the root. This is called sift-up, also bubble-up or percolate-up, and it does at most one comparison and one swap per level.

Inserting 5, 3, 8 and 1 into an empty min-heap, step by step in the model:

The root holds the minimum. To remove it, take the root out, move the last element of the array into the root, and shrink the array by one. The tree is complete again, but the new root is probably too large. Compare it with its smaller child (larger, in a max-heap); if the child belongs above it, swap them and repeat one level down. This is sift-down, also called heapify-down. Each level costs two comparisons, one to pick the child and one to compare with it.

Extracting the minimum from the heap above returns 1 and leaves [3, 5, 8], after 2 comparisons and 1 swap.

Python’s heapq.heappop uses a variation: it moves the smaller child up all the way to a leaf without comparing with the moved element, then sifts that element back up a little. Its source notes that this saves comparisons on average, since the element taken from the end usually belongs near the bottom. The values come out in the same order; the arrays in between can differ.

Turning an unsorted array into a heap by inserting its elements one at a time costs O(n log n) in the worst case. Floyd’s method is faster: treat the array as a complete tree as it stands, notice that every leaf (the second half of the array) is already a one-element heap, and sift down each parent, from the last parent back to the root. When a node is sifted down, both its subtrees are already heaps.

Most nodes are near the bottom and can only move a short distance: half are leaves and do nothing, a quarter move at most one level, an eighth at most two. Summed up, the work is O(n), and the number of comparisons stays below 2n. Counting comparisons in the model, on the same values in both cases:

Heapsort sorts an array in place with a heap. Build a max-heap from the array; the largest value is now at index 0. Swap it with the last element of the heap, shrink the heap by one so that value is fixed in its final place, and sift down the new root. Repeat until the heap is empty. The array ends up in ascending order (a min-heap gives descending order, as the simulator shows when you heapsort a min-heap).

Heapsort runs in O(n log n) time in the worst case and needs only O(1) extra memory, which few sorts manage at once. It is not stable, and in practice it is usually slower than a good quicksort because its accesses jump around the array and miss the cache. Its guaranteed worst case is why introsort, the algorithm behind many C++ std::sort implementations, falls back to heapsort when quicksort’s recursion gets too deep.

A priority queue lets you add items with priorities and always take the highest-priority item next. The binary heap is its standard implementation, and it appears wherever “what next?” has to be answered quickly:

• Graph algorithms: Dijkstra’s shortest paths, Prim’s minimum spanning tree and A* search take the closest unvisited node from a heap.
• Scheduling: timers and event simulations pop the earliest deadline; operating system and job schedulers pick the next task by priority.
• Top-k: keep a min-heap of size k while streaming values to find the k largest in O(n log k) time and O(k) memory.
• Merging: merging k sorted lists or files, as databases and external sorts do, keeps the head of each list in a heap of size k.
• Running median: a max-heap of the lower half and a min-heap of the upper half give the median of a stream at any moment.
• Compression: building a Huffman code repeatedly combines the two least frequent symbols, taken from a min-heap.

A d-ary heap gives each node d children instead of two. The tree is shallower, so inserts and decrease-key are faster, while extract does more comparisons per level; 4-ary heaps are often faster in practice thanks to better cache use. Binomial, pairing and Fibonacci heaps support merging two heaps quickly; the Fibonacci heap (Fredman and Tarjan, 1987) does decrease-key in O(1) amortised time, which improves the theoretical bound of Dijkstra’s algorithm, though its constant factors mean binary heaps usually win in practice.

Heap questions are common in coding interviews, usually as a tool rather than a data structure to implement: kth largest element, top k frequent elements, k closest points, merge k sorted lists, task scheduling, meeting rooms, and the median of a data stream with two heaps. Know which library heap your language provides and its default order, the O(n log k) cost of keeping a size-k heap, and why that beats sorting when k is small.

When asked to implement one, write the array index formulas, sift-up and sift-down, and mention that build-heap is O(n). The classic follow-up is the proof sketch of that bound, or why heapsort is not stable.