Heap Sort

1function heapSort(arr) {
2  const n = arr.length;
3 
4  // Step 1: Build max heap bottom-up in O(n) time
5  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
6    heapify(arr, n, i);
7  }
8 
9  // Step 2: Extract elements one by one from heap
10  for (let i = n - 1; i > 0; i--) {
11    // Move current maximum (root) to the end
12    [arr[0], arr[i]] = [arr[i], arr[0]];
13 
14    // Restore max heap on the reduced array
15    heapify(arr, i, 0);
16  }
17 
18  return arr;
19}
20 
21function heapify(arr, n, i) {
22  let largest = i;
23  const left = 2 * i + 1;
24  const right = 2 * i + 2;
25 
26  // Check if left child exists and is greater than largest
27  if (left < n && arr[left] > arr[largest]) {
28    largest = left;
29  }
30 
31  // Check if right child exists and is greater than largest
32  if (right < n && arr[right] > arr[largest]) {
33    largest = right;
34  }
35 
36  // If largest is not the current root node, swap and continue heapifying
37  if (largest !== i) {
38    [arr[i], arr[largest]] = [arr[largest], arr[i]];
39    heapify(arr, n, largest);
40  }
41}
42 
43// Example usage:
44// heapSort([4, 10, 3, 5, 1]); // [1, 3, 4, 5, 10]