1function heapSort(arr) {
2  const n = arr.length;
3  
4  // Build max heap (rearrange array)
5  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
6    heapify(arr, n, i);
7  }
8  
9  // Extract elements from heap one by one
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// To heapify a subtree rooted with node i
22function heapify(arr, n, i) {
23  let largest = i; // Initialize largest as root
24  const left = 2 * i + 1;
25  const right = 2 * i + 2;
26  
27  // If left child is larger than root
28  if (left < n && arr[left] > arr[largest]) {
29    largest = left;
30  }
31  
32  // If right child is larger than largest so far
33  if (right < n && arr[right] > arr[largest]) {
34    largest = right;
35  }
36  
37  // If largest is not root
38  if (largest !== i) {
39    [arr[i], arr[largest]] = [arr[largest], arr[i]];
40    
41    // Recursively heapify the affected subtree
42    heapify(arr, n, largest);
43  }
44}