Heap Sort Visualization & Heapify Simulator

Q: What is the time complexity of heap sort?

O(n log n) in all cases, with O(1) extra space.

About this visualization

Heap sort turns the array into a max-heap (every parent is at least as large as its children), then swaps the root, which is the maximum, to the end and restores the heap on the remaining items. It sorts in place with guaranteed $O(n \log n)$ time.

How it works

Build a max-heap by heapifying every parent from the last one up to the root.
Swap the root with the last item of the heap; that item is now in its final place.
Heapify the new root down to restore the heap and repeat.

Worked example

Build a max-heap from [4, 10, 3, 5, 1]: heapify index 1 keeps 10; heapify the root swaps 4 with 10 and then with 5 → [10, 5, 3, 4, 1]. Swap the root with the last item → [1, 5, 3, 4, 10] and heapify the first four items, and so on until sorted: [1, 3, 4, 5, 10].

Enter these numbers in the simulator above to see every step.

Complexity and properties

Best case	$O(n \log n)$
Average case	$O(n \log n)$
Worst case	$O(n \log n)$
Space	$O(1)$
Stable	No
In-place	Yes

When to use it

Sorting in place with a guaranteed $O(n \log n)$ worst case.
Understanding binary heaps, which also power priority queues.
Exam questions asking for the array after building the heap.

Frequently asked questions

What is the time complexity of heap sort?

$O(n \log n)$ in all cases, with $O(1)$ extra space.

Is heap sort stable?

No. Moving the root to the end can change the order of equal items.

What is heapify?

Heapify restores the heap property for a node by swapping it with its larger child until both children are smaller.