堆排序

概要

堆的表示形式

逻辑结构的表示如下：

在物理数据层的表示如下：

堆排序，是选择排序的优化版本，利用数据结构——树，对数据进行管理。

以大顶堆为例:

1. 通过构建大顶堆
2. 将堆顶的最大数拿出，与堆底的叶子节点进行交换
3. 接着，树剪掉最大数的叶子
4. 再对堆进行调整，重新变成大顶堆
5. 返回步骤2，以此循环，直至取出所有数

效果图

caution

在实现代码时，构建大顶堆时，先保证左右子树的有序，再逐步扩大到整棵树。

构建大顶堆

从第一个非叶子节点开始，调整它所在的子树

调整下标1节点的子树后，向上继续调整它的父节点（下标0）所在的子树

最后，完成整个树的调整，构建好大顶堆。

逐个抽出堆顶最大值

堆顶数字与最末尾的叶子数字交换，抽出堆顶数字9。

此时，数字9位置固定下来，树剪掉9所在的叶子。然后，重新构建大顶堆。

大顶堆构建好后，继续抽出堆顶数字8，然后再次重新构建大顶堆。

最后，所有节点抽出完成，代表排序已完成。

解法

以大顶堆为例，对数组进行升序排序

注意点

树的最后一个非叶子节点：(arr.length / 2) - 1
非叶子节点i的左叶子节点： i*2+1
非叶子节点i的右叶子节点： i*2+2

function heapSort(arr){

    // 初次构建大顶堆
    for(let i = Math.floor(arr.length/2) - 1; i >= 0; i--){
        // 开始的第一个节点是 树的最后一个非叶子节点
        // 从构建子树开始，逐步调整
        buildHeap(arr, i, arr.length);
    }

    // 逐个抽出堆顶最大值
    for(let j = arr.length -1 ; j > 0; j--){
        swap(arr, 0, j); // 抽出堆顶（下标0）的值，与最后的叶子节点进行交换
        // 重新构建大顶堆
        // 由于上一步的堆顶最大值已经交换到数组的末尾，所以，它的位置固定下来
        // 剩下要比较的数组，长度是j,所以这里的值length == j
        buildHeap(arr, 0, j); 
    }

    return arr;

    
    // 构建大顶堆
    function buildHeap(arr, i, length){
        let tmp = arr[i]; 
        
        for(let k = 2*i+1; k < length; k = 2*k+1){
            // 先判断左右叶子节点，哪个比较大
            if(k+1 < length && arr[k+1] > arr[k]){
                k++;
            }
            // 将最大的叶子节点，与当前的值进行比较
            if(arr[k] > tmp){
                // k节点大于i节点的值，需要交换
                arr[i] = arr[k]; // 将k节点的值与i节点的值交换
                i = k; // 注意：交换后，当前值tmp的下标是k，所以需要更新
            }else{
                // 如果tmp大于左右子节点，则它们的子树也不用判断，都是小于当前值
                break;
            }
            
        }

        // i是交换后的下标，更新为tmp
        arr[i] = tmp;
    }


    // 交换值
    function swap(arr, i, j){
        const tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

参考

• 图解排序算法(三)之堆排序