【JavaScript 算法】堆排序：优先队列的实现

堆排序（Heap Sort）是一种基于堆数据结构的排序算法，具有较好的时间复杂度表现。堆是一种特殊的完全二叉树，分为最大堆和最小堆。堆排序通过构建最大堆或最小堆来实现排序过程。本文将详细介绍堆排序算法的原理、实现及其应用。

一、算法原理

堆排序的基本思想是将待排序的数组构建成一个最大堆或最小堆，然后通过堆的删除操作将堆顶元素逐个取出，得到一个有序序列。

堆的定义

• 最大堆：每个节点的值都大于或等于其子节点的值。
• 最小堆：每个节点的值都小于或等于其子节点的值。

堆排序的步骤

1. 构建最大堆：将数组重新组织成一个最大堆。
2. 交换堆顶元素与末尾元素：将堆顶元素（最大值）与末尾元素交换，将最大值移到数组末尾。
3. 调整堆：重新调整堆，保持最大堆性质。
4. 重复步骤2和3，直到堆的大小为1，排序完成。

二、算法实现

构建最大堆

/**
 * 调整堆
 * @param {number[]} arr - 数组
 * @param {number} len - 堆的有效大小
 * @param {number} i - 当前节点的索引
 */
function heapify(arr, len, i) {
  let largest = i; // 初始化当前节点为最大值
  const left = 2 * i + 1; // 左子节点索引
  const right = 2 * i + 2; // 右子节点索引

  // 如果左子节点存在且大于当前节点，则更新最大值
  if (left < len && arr[left] > arr[largest]) {
    largest = left;
  }

  // 如果右子节点存在且大于当前节点，则更新最大值
  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }

  // 如果最大值不是当前节点，则交换并继续调整堆
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, len, largest);
  }
}

/**
 * 堆排序算法
 * @param {number[]} arr - 待排序的数组
 * @return {number[]} - 排序后的数组
 */
function heapSort(arr) {
  const len = arr.length;

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

  // 逐个将堆顶元素移到末尾，然后调整堆
  for (let i = len - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 交换堆顶元素与末尾元素
    heapify(arr, i, 0); // 调整堆
  }

  return arr;
}

// 示例
const arr = [3, 19, 1, 14, 8, 7];
console.log(heapSort(arr)); // 输出: [1, 3, 7, 8, 14, 19]

注释说明：

1. 调整堆：
   • heapify(arr, len, i)：调整堆，使其保持最大堆性质，接受数组、堆的有效大小和当前节点的索引作为参数。
   • let largest = i;：初始化当前节点为最大值。
   • const left = 2 * i + 1; const right = 2 * i + 2;：计算左、右子节点的索引。
   • if (left < len && arr[left] > arr[largest]) largest = left;：如果左子节点大于当前节点，更新最大值。
   • if (right < len && arr[right] > arr[largest]) largest = right;：如果右子节点大于当前节点，更新最大值。
   • if (largest !== i) [arr[i], arr[largest]] = [arr[largest], arr[i]]; heapify(arr, len, largest);：如果最大值不是当前节点，则交换并继续调整堆。
2. 堆排序：
   • heapSort(arr)：堆排序算法，接受待排序的数组作为参数，返回排序后的数组。
   • const len = arr.length;：获取数组长度。
   • for (let i = Math.floor(len / 2) - 1; i >= 0; i--) heapify(arr, len, i);：从最后一个非叶子节点开始构建最大堆。
   • for (let i = len - 1; i > 0; i--) [arr[0], arr[i]] = [arr[i], arr[0]]; heapify(arr, i, 0);：逐个将堆顶元素移到末尾，然后调整堆。

三、应用场景

1. 优先队列：堆可以实现优先队列，优先级最高的元素总是位于堆顶。
2. 任务调度：堆可以用于任务调度，将优先级最高的任务最先处理。
3. 实时数据流排序：在实时数据流中，使用堆可以高效地维护一个有序的数据集。

四、总结

堆排序是一种基于堆数据结构的高效排序算法，通过构建最大堆或最小堆，利用堆的特性实现排序过程。理解和掌握堆排序算法，可以有效解决优先队列、任务调度和实时数据流排序等问题。