1/**
2 * Heap Sort implementation for JavaScript arrays
3 * @param {Array} arr - The array to sort
4 * @returns {Array} - A new sorted array
5 */
6function heapSort(arr) {
7  // Create a copy to avoid modifying the original array
8  const result = [...arr];
9  const n = result.length;
10  
11  // Build max heap
12  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
13    heapify(result, n, i);
14  }
15  
16  // Extract elements from heap one by one
17  for (let i = n - 1; i > 0; i--) {
18    // Move current root to end
19    [result[0], result[i]] = [result[i], result[0]];
20    
21    // Call heapify on the reduced heap
22    heapify(result, i, 0);
23  }
24  
25  return result;
26}
27
28/**
29 * Function to heapify a subtree rooted at index i
30 * @param {Array} arr - The array to heapify
31 * @param {Number} n - Size of the heap
32 * @param {Number} i - Root index of the subtree to heapify
33 */
34function heapify(arr, n, i) {
35  let largest = i; // Initialize largest as root
36  const left = 2 * i + 1; // Left child
37  const right = 2 * i + 2; // Right child
38  
39  // If left child is larger than root
40  if (left < n && arr[left] > arr[largest]) {
41    largest = left;
42  }
43  
44  // If right child is larger than largest so far
45  if (right < n && arr[right] > arr[largest]) {
46    largest = right;
47  }
48  
49  // If largest is not root
50  if (largest !== i) {
51    // Swap and continue heapifying
52    [arr[i], arr[largest]] = [arr[largest], arr[i]];
53    heapify(arr, n, largest);
54  }
55}