Heap Sort Algorithm
arr = [4, 10, 3, 5, 1]
No Extra Space: O(1)
Visual Representation
The steps are as follows:- Create
Max Heap.- Ignore the leaf nodes.
- Run Loop in
Reverse. - For each node we create it a
maxHeap.
- Sort
- Extract
maximumelement. - Store at end.
HeapifyDown- Repeat till whole array is
sorted.
- Extract
Output: arr = [1, 4, 3, 5, 10]
- Create
Code
let arr = [10, 4, 5, 1, 3];
function heapSort(arr) {
let n = arr.length;
// create a MaxHeap
for(let i=n-1; i >= 0; i--){
heapifyDown(arr, i, n);
}
// sort the array
for(let i = n-1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapifyDown(arr, 0, i);
}
return arr
}
function heapifyDown(arr, i, n){
let largest = i;
let left = (2 * i) + 1;
let right = (2 * i) + 2;
if(left < n && arr[left] > arr[largest]) {
largest = left;
}
if(right < n && arr[right] > arr[largest]) {
largest = right;
}
if(largest != i){
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapifyDown(arr, largest, n);
}
}
const sortedArray = heapSort(arr);
console.log(sortedArray);
Dry Run
Input:
Initial array = [10, 4, 5, 1, 3] Operation = Build Max Heap
State Transitions:
i = 4 → left=9, right=10 → no change → [10, 4, 5, 1, 3] i = 3 → left=7, right=8 → no change → [10, 4, 5, 1, 3] i = 2 → left=5, right=6 → no change → [10, 4, 5, 1, 3] i = 1 → left=3, right=4 → compare arr[3]=1, arr[4]=3 → largest=4 → swap → [10, 3, 5, 1, 4] i = 4 heapifyDown: no change → [10, 3, 5, 1, 4] i = 0 → left=1 (3), right=2 (5) → largest=2 → swap → [5, 3, 10, 1, 4] heapifyDown(2): no change → [5, 3, 10, 1, 4]
Final Output: [5, 3, 10, 1, 4]
Final State: Max Heap = [5, 3, 10, 1, 4]
Input:
Heap = [5, 3, 10, 1, 4] Swap max with last element
State Transitions:
Swap arr[0] with arr[4] → [4, 3, 10, 1, 5] heapifyDown(0, n=4): left=1 (3), right=2 (10) → largest=2 → swap → [10, 3, 4, 1, 5] heapifyDown(2, n=4): no change
Final Output: [10, 3, 4, 1, 5]
Final State: Heap after 1st extraction
Input:
Heap = [10, 3, 4, 1, 5] Swap max with last element in heap size 4
State Transitions:
Swap arr[0] with arr[3] → [1, 3, 4, 10, 5] heapifyDown(0, n=3): left=1 (3), right=2 (4) → largest=2 → swap → [4, 3, 1, 10, 5] heapifyDown(2, n=3): no change
Final Output: [4, 3, 1, 10, 5]
Final State: Heap after 2nd extraction
Input:
Heap = [4, 3, 1, 10, 5] Swap max with last element in heap size 3
State Transitions:
Swap arr[0] with arr[2] → [1, 3, 4, 10, 5] heapifyDown(0, n=2): left=1 (3), right=2 (out of range) → largest=1 → swap → [3, 1, 4, 10, 5] heapifyDown(1, n=2): no change
Final Output: [3, 1, 4, 10, 5]
Final State: Heap after 3rd extraction
Input:
Heap = [3, 1, 4, 10, 5] Swap max with last element in heap size 2
State Transitions:
Swap arr[0] with arr[1] → [1, 3, 4, 10, 5] heapifyDown(0, n=1): no change
Final Output: [1, 3, 4, 10, 5]
Final State: Fully Sorted Array
