Sort an array in increasing order, in place. Heap sort uses a max heap built inside the array itself.
DSA Animator › DSA Revision › Sorting Algorithms › Heap Sort
Remember: build a max heap, then move the root to the end, again and again. In place, guaranteed n log n, but not stable. The video solves Heap Sort (LeetCode 912, Medium) with the Max Heap pattern from the Sorting Algorithms topic, and you can replay every step in the interactive Heap Sort animation.
Sort an array in increasing order, in place. Heap sort uses a max heap built inside the array itself.
For 4, 10, 3, 5, 1, the result is 1, 3, 4, 5, 10.
Repeatedly scanning for the maximum is selection sort, which is O of n squared. A heap finds the maximum in O of log n.
First, turn the array into a max heap, so every parent is at least as big as its children. Build it bottom up by sifting down every parent, from the last one to the root. Now the largest value sits at index 0. Swap it with the last element of the heap, which is its final position, and shrink the heap. Sift the new root down to restore the heap, and repeat.
Heapify: 10 is already bigger than its children, then the root 4 sinks below 10 and 5. The heap is 10, 5, 3, 4, 1. Swap 10 to the end, then sift 1 down, giving 5, 4, 3, 1, and 10 is final. Swap 5 to the end, and sift, giving 4, 1, 3. Then 4, then 3 move to their places. The array is 1, 3, 4, 5, 10.
In code, loop i from n over 2 minus 1 down to 0, and sift down each index. Then loop end from n minus 1 down to 1: swap a of 0 with a of end, and sift down the root within end. Sift down swaps a node with its larger child until it is bigger than both. It's O of n log n time and O of 1 extra space, but not stable.
Remember: build a max heap, then move the root to the end, again and again. In place, guaranteed n log n, but not stable.