loading
loading
loading
Computer Science / Algorithms
Part of the Heaps & Priority Queues Learning Experience →Build a max-heap, then repeatedly extract the maximum into a shrinking sorted tail — O(n log n) with O(1) auxiliary space.
A binary heap is a tree stored implicitly in a plain array, with no pointers at all: for a node at index i, its children live at indices 2i+1 and 2i+2, and its parent lives at index ⌊(i−1)/2⌋. A max-heap additionally guarantees every parent is ≥ both its children — so the largest value is always at the root, index 0. Heap sort works in two phases. First, it builds a max-heap out of the raw input by sifting every non-leaf node down into place, from the last non-leaf up to the root. Then it repeatedly swaps the root (the current maximum) with the last element of the still-active heap, shrinks the heap by one, and sifts the new root down to restore the max-heap property — each extraction places one more value in its final sorted position, at the end of the array. This visualizer shows both views at once: a tree diagram (the logical structure) and the array strip beneath it (the actual storage) — watch how a swap in the tree is the exact same swap in the array underneath. Press Shuffle to generate a new random array and watch both phases repeat.
Heap sort is the only one of the three that gets O(n log n) guaranteed in every case AND O(1) extra space, at the same time. Merge Sort also guarantees O(n log n) in every case, but needs O(n) auxiliary space for its merge buffer. Quick Sort needs only O(log n) space on average, but this platform's last-element pivot choice makes its worst case O(n²) on already-sorted input — a guarantee heap sort doesn't need a lucky pivot to make.
Sifting swaps elements across the tree based purely on value comparisons, with no awareness of — or care for — where two equal values originally stood relative to each other. A swap during sift-down can easily move one equal-valued element past another, so heap sort makes no promise about preserving original order.
A binary heap is a complete tree — every level is filled left to right before the next level starts — which means the tree can be laid out in an array with no gaps and no pointers at all: reading the array left to right visits the tree level by level, top to bottom, and that layout is exactly what makes 2i+1 / 2i+2 / ⌊(i−1)/2⌋ always correct, for any complete binary tree of any size.