# Heap Sort visualised: max-heap and siftDown

> Interactive Heap Sort with tree view: build a max-heap, swap the root with the last heap element and run siftDown. Guaranteed O(n log n), in-place.

Address: https://marckimmel.de/en/informatik/sortieralgorithmen/heap-sort
Deutsche Fassung: https://marckimmel.de/informatik/sortieralgorithmen/heap-sort.md

Builds a max-heap, then repeatedly extracts the largest element to the end.

Heap Sort treats the array as a binary tree: the element at index i has its children at indices 2i+1 and 2i+2. The first phase builds a max-heap by calling siftDown on every internal node from bottom up: the element is compared with the larger of its children and swapped down as long as a child is larger. After the build the maximum sits at the root (index 0). The second phase repeatedly swaps the root with the last heap element, shrinks the heap by one (the swapped element is now considered sorted) and restores the heap property by sifting down the new root. This continues until the heap is empty. The heap build costs O(n) and the n-1 sift-downs cost O(log n) each, producing the guaranteed total runtime O(n log n) in every case. Heap Sort runs in-place (O(1) extra memory) but is not stable.

First choice when the worst case must stay guaranteed at O(n log n) and no extra memory is available, because Heap Sort runs fully in-place. Suitable for embedded and real-time systems and serves as the safety net inside Introsort when Quick Sort recurses too deep.

## Related

- [Sorting Algorithms](https://marckimmel.de/en/informatik/sortieralgorithmen.md)