编辑代码

// 堆排序主函数
function heapSort(arr) {
  const n = arr.length;

  // 构建小根堆
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // 一个个从堆顶取出元素
  for (let i = n - 1; i > 0; i--) {
    // 将当前根节点(最小值)与未排序部分的最后一个元素交换
    swap(arr, 0, i);
    // 重新调整堆,排除刚才交换的元素
    heapify(arr, i, 0);
  }
}

// 将数组转换为小根堆
function heapify(arr, n, i) {
  let smallest = i; // 初始化根节点索引为最小值索引
  const left = 2 * i + 1; // 左子节点索引
  const right = 2 * i + 2; // 右子节点索引

  // 如果左子节点小于根节点,更新最小值索引
  if (left < n && arr[left] < arr[smallest]) {
    smallest = left;
  }

  // 如果右子节点小于根节点,更新最小值索引
  if (right < n && arr[right] < arr[smallest]) {
    smallest = right;
  }

  // 如果最小值索引不等于根节点索引,交换根节点与最小值
  if (smallest !== i) {
    swap(arr, i, smallest);
    // 继续调整被交换的子树
    heapify(arr, n, smallest);
  }
}

// 交换数组中两个元素的位置
function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

// 示例
const arr = [12, 11, 13, 5, 6, 7];
console.log("原始数组:", arr);

heapSort(arr);

console.log("排序后的数组:", arr);