We start with an unsorted array [64, 34, 25, 12, 22, 11, 90]. The first step in heap sort is to build a max heap from this array.
64
34
25
12
22
11
90
Step 2: Building Max Heap
To build a max heap, we organize the elements in a tree structure where each parent node is greater than or equal to its child nodes. The array representation of a heap tree places the root at index 0, and for any node at index i, its left child is at 2i+1 and right child at 2i+2.
90
34
64
12
22
11
25
Step 3: First Extraction
In heap sort, we extract the maximum element (root) and place it at the end of the array. Then we re-heapify the remaining elements. Here, we swap 90 with the last element 25, and remove 90 from the heap.
64
34
25
12
22
11
90
Step 4: Second Extraction
After re-heapifying, 64 is now at the root. We swap it with the last element of the current heap (11) and remove it from the heap.
34
22
25
12
11
64
90
Step 5: Third Extraction
After re-heapifying, 34 is now at the root. We swap it with the last element of the current heap (11) and remove it from the heap.
25
22
11
12
34
64
90
Step 6: Final Sorted Array
We continue this process until all elements are extracted from the heap. The final result is a sorted array in ascending order.