Heap Sort Visualization

1function heapSort(arr) {
2    const n = arr.length;
3    
4    // Build heap (rearrange array)
5    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
6      heapify(arr, n, i);
7    }
8    
9    // One by one extract an element from heap
10    for (let i = n - 1; i > 0; i--) {
11      // Move current root to end
12      [arr[0], arr[i]] = [arr[i], arr[0]];
13      
14      // Call max heapify on the reduced heap
15      heapify(arr, i, 0);
16    }
17    
18    return arr;
19  }
20  
21  function heapify(arr, n, i) {
22    // Initialize largest as root
23    let largest = i;
24    
25    // Left child index
26    const left = 2 * i + 1;
27    
28    // Right child index
29    const right = 2 * i + 2;
30    
31    // If left child is larger than root
32    if (left < n && arr[left] > arr[largest]) {
33      largest = left;
34    }
35    
36    // If right child is larger than largest so far
37    if (right < n && arr[right] > arr[largest]) {
38      largest = right;
39    }
40    
41    // If largest is not root
42    if (largest !== i) {
43      // Swap
44      [arr[i], arr[largest]] = [arr[largest], arr[i]];
45      
46      // Recursively heapify the affected sub-tree
47      heapify(arr, n, largest);
48    }
49  }