在Javascript中实现递归maxHeap

function maxHeapify(arr, n, i) {
  let largest = i; // 初始化最大值为当前节点
  const left = 2 * i + 1; // 左子节点的索引
  const 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]];
    // 递归调用maxHeapify函数，继续向下调整最大堆
    maxHeapify(arr, n, largest);
  }
}

function buildMaxHeap(arr) {
  const n = arr.length;
  // 从最后一个非叶子节点开始，依次向上构建最大堆
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    maxHeapify(arr, n, i);
  }
}

function heapSort(arr) {
  const n = arr.length;
  // 构建最大堆
  buildMaxHeap(arr);

  // 从最后一个节点开始，依次将最大值交换到数组末尾，并重新调整堆
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    maxHeapify(arr, i, 0);
  }

  return arr;
}

// 示例用法
const arr = [4, 10, 3, 5, 1];
const sortedArr = heapSort(arr);
console.log(sortedArr); // 输出 [1, 3, 4, 5, 10]