带比较器的原地堆排序

功能说明

该示例用堆排序对数组做原地排序。它先把整个数组调整为大顶堆，然后不断把堆顶最大值交换到末尾，再对剩余部分重新下沉，最终得到升序结果。整个过程只使用常数额外空间，适合内存敏感或需要避免递归栈风险的场景。

关键代码

建堆从最后一个非叶子节点 (size >> 1) - 1 开始向前调用 siftDown，保证每个子树都满足堆性质。排序阶段每次把下标 0 与当前末尾交换，然后缩小堆范围并再次下沉根节点。siftDown 比较左右子节点，选择较大者与当前节点交换，直到没有更小的子节点为止。比较器由调用方注入，因此同一套代码可以输出升序或降序。

使用注意

堆排序不稳定，相同键的元素顺序会改变。比较器必须形成全序，返回负数表示第一个参数应排在前面。数组会被原地修改并返回，调用方不要同时持有旧顺序的假设。建堆阶段是 O(n)，整体 O(n log n)，但常数通常比内置排序大，实际项目应优先使用 Array.prototype.sort，仅在需要控制内存或教学演示时选用。

验证方式

对普通数字数组断言升序结果，对三元数组使用反向比较器断言降序结果。测试空数组、单元素、已排序与全部相等数组。再用随机数组与内置排序逐项比较，并检查排序后元素多重集与输入一致，确认没有丢元素或重复写入。

代码示例

export function heapSort(items, compare = defaultCompare) {
  if (!Array.isArray(items)) throw new TypeError("items must be an array");
  if (typeof compare !== "function") throw new TypeError("compare must be a function");
  const size = items.length;
  for (let root = (size >> 1) - 1; root >= 0; root -= 1) {
    siftDown(items, root, size, compare);
  }
  for (let end = size - 1; end > 0; end -= 1) {
    swap(items, 0, end);
    siftDown(items, 0, end, compare);
  }
  return items;
}

function siftDown(items, root, size, compare) {
  let current = root;
  while (true) {
    const left = current * 2 + 1;
    const right = left + 1;
    let largest = current;
    if (left < size && compare(items[left], items[largest]) > 0) largest = left;
    if (right < size && compare(items[right], items[largest]) > 0) largest = right;
    if (largest === current) return;
    swap(items, current, largest);
    current = largest;
  }
}

function swap(items, left, right) {
  const temporary = items[left];
  items[left] = items[right];
  items[right] = temporary;
}

function defaultCompare(left, right) {
  return left < right ? -1 : left > right ? 1 : 0;
}

const numbers = [9, 4, 7, 1, 8, 4, 2];
console.log(heapSort(numbers));
console.log(heapSort([3, 1, 2], (left, right) => right - left));