Sort 8 values with a heap built in place. Read the array as a tree: the children of index i sit at 2i + 1 and 2i + 2. First make every parent larger than its children, then pull the maximum off the top 8 times.
Heap sort on 4, 10, 3, 5, 1, 8, 7, 2.
Index 3 holds 5. Its larger child is 2 at index 7. 5 is already at least as large, so the heap property holds here.
Parent 5 at 3, larger child 2 at 7. Stop.
Index 2 holds 3. Its larger child is 8 at index 5. 8 > 3, so they swap and 3 sinks to index 5.
Parent 3 at 2, larger child 8 at 5. Swap.
Index 1 holds 10. Its larger child is 5 at index 3. 10 is already at least as large, so the heap property holds here.
Parent 10 at 1, larger child 5 at 3. Stop.
Index 0 holds 4. Its larger child is 10 at index 1. 10 > 4, so they swap and 4 sinks to index 1.
Parent 4 at 0, larger child 10 at 1. Swap.
Index 1 holds 4. Its larger child is 5 at index 3. 5 > 4, so they swap and 4 sinks to index 3.
Parent 4 at 1, larger child 5 at 3. Swap.
Index 3 holds 4. Its larger child is 2 at index 7. 4 is already at least as large, so the heap property holds here.
Parent 4 at 3, larger child 2 at 7. Stop.
Every parent beats its children: a max-heap, with the maximum 10 at index 0.
Max-heap built, maximum 10.
Swap the root 10 with the last heap slot, index 7. 10 is now in its final place and the heap shrinks to 7 slots. The new root must sift down.
10 moves to index 7, heap size 7.
Index 0 holds 2. Its larger child is 8 at index 2. 8 > 2, so they swap and 2 sinks to index 2.
Parent 2 at 0, larger child 8 at 2. Swap.
Index 2 holds 2. Its larger child is 7 at index 6. 7 > 2, so they swap and 2 sinks to index 6.
Parent 2 at 2, larger child 7 at 6. Swap.
Swap the root 8 with the last heap slot, index 6. 8 is now in its final place and the heap shrinks to 6 slots. The new root must sift down.
8 moves to index 6, heap size 6.
Index 0 holds 2. Its larger child is 7 at index 2. 7 > 2, so they swap and 2 sinks to index 2.
Parent 2 at 0, larger child 7 at 2. Swap.
Index 2 holds 2. Its larger child is 3 at index 5. 3 > 2, so they swap and 2 sinks to index 5.
Parent 2 at 2, larger child 3 at 5. Swap.
Swap the root 7 with the last heap slot, index 5. 7 is now in its final place and the heap shrinks to 5 slots. The new root must sift down.
7 moves to index 5, heap size 5.
Index 0 holds 2. Its larger child is 5 at index 1. 5 > 2, so they swap and 2 sinks to index 1.
Parent 2 at 0, larger child 5 at 1. Swap.
Index 1 holds 2. Its larger child is 4 at index 3. 4 > 2, so they swap and 2 sinks to index 3.
Parent 2 at 1, larger child 4 at 3. Swap.
Swap the root 5 with the last heap slot, index 4. 5 is now in its final place and the heap shrinks to 4 slots. The new root must sift down.
5 moves to index 4, heap size 4.
Index 0 holds 1. Its larger child is 4 at index 1. 4 > 1, so they swap and 1 sinks to index 1.
Parent 1 at 0, larger child 4 at 1. Swap.
Index 1 holds 1. Its larger child is 2 at index 3. 2 > 1, so they swap and 1 sinks to index 3.
Parent 1 at 1, larger child 2 at 3. Swap.
Swap the root 4 with the last heap slot, index 3. 4 is now in its final place and the heap shrinks to 3 slots. The new root must sift down.
4 moves to index 3, heap size 3.
Index 0 holds 1. Its larger child is 3 at index 2. 3 > 1, so they swap and 1 sinks to index 2.
Parent 1 at 0, larger child 3 at 2. Swap.
Swap the root 3 with the last heap slot, index 2. 3 is now in its final place and the heap shrinks to 2 slots. The new root must sift down.
3 moves to index 2, heap size 2.
Index 0 holds 1. Its larger child is 2 at index 1. 2 > 1, so they swap and 1 sinks to index 1.
Parent 1 at 0, larger child 2 at 1. Swap.
Swap the root 2 with the last heap slot, index 1. 2 is now in its final place and the heap shrinks to 1 slot. The new root must sift down.
2 moves to index 1, heap size 1.
Sorted. 27 comparisons and 20 swaps. Building the heap is O(n) and each of the n extractions sifts down at most log n levels: O(n log n) in every case, in place, but not stable.
Sorted after 27 comparisons and 20 swaps.