NodeJS实现堆排序算法

​ NodeJS实现堆排序算法

以下是使用 Node.js 实现堆排序算法的示例代码：

// 堆排序函数
function heapSort(arr) {
    // 构建最大堆
    buildMaxHeap(arr);

    // 依次取出最大堆的根节点（最大值），并调整堆结构
    for (let i = arr.length - 1; i > 0; i--) {
        // 将当前根节点（最大值）与最后一个节点交换位置
        [arr[0], arr[i]] = [arr[i], arr[0]];
        
        // 调整堆，使剩余元素继续保持最大堆的性质
        heapify(arr, 0, i);
    }
}

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

// 调整堆
function heapify(arr, i, heapSize) {
    const left = 2 * i + 1; // 左子节点索引
    const right = 2 * i + 2; // 右子节点索引
    let largest = i; // 记录最大值的索引

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

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

    // 如果最大值索引不等于当前节点索引，则交换当前节点与最大值节点的值，并递归调整堆
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, largest, heapSize);
    }
}

// 测试堆排序算法
const arr = [12, 11, 13, 5, 6, 7];
console.log('原始数组：', arr);

heapSort(arr);
console.log('排序后的数组：', arr);

这段代码定义了三个函数：heapSort 用于执行堆排序，buildMaxHeap 用于构建最大堆，heapify 用于调整堆的结构以保持最大堆的性质。然后通过 heapSort 函数对输入数组进行排序，并输出结果。

​

​