搞定JavaScript算法系列--堆排序

在做堆 排序 之前需要先理解数据结构中“堆”的概念，上面两篇文章中先后介绍的数据结构中的树，二叉树以及堆的相关知识。

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父结点。

算法步骤

(1) 创建一个大根堆H[0, ..., n-1]，此时H[0]为数组里的最大值（共有n个元素）。

(2) 把堆首和堆尾互换（即H[0]和H[n-1]交换），这样H[n-1]为堆H[0, ..., n-1]的最大值，同时H[0, ..., n-2]为无序树。

(3) 调整H[0, ..., n-2]为大根堆，然后再次交换首尾元素。

(4) 重复步骤(3)直到最后一个元素，得到一个升序数组H[0, ..., n-1]。

算法原理

将数组看成一个完全二叉树，对于该完全二叉树只需要遍历一半的值，进行循环比对，把最大的结点赋值到根的位置，然后把根部的值和最后一个数值交换，排除最后一个数值继续打造大顶堆，最终形成一个小顶堆的算法。

• 设某结点序号为i,则其父结点为⌊i/2⌋，2i为左子结点序号，2i+1为右子结点序号。其中，⌊⌋为向下取整符号。
• 当存储了n个元素时，⌊n/2⌋+1、⌊n/2⌋+1、···、n为叶结点。

注：此处不理解可以阅读 《重温数据结构系列--二叉树、堆》 中完全二叉树的特性及其顺序表存储。

实现过程

建堆，调整堆的结构（父结点的值大于孩子结点的值），排序。下面程序由JavaScript实现该过程。

// 创建堆，其实是对data数组做一个结构调整，使其具有堆的特性
function buildHeap(data) {
    var len = data.length;
    for(var i=Math.floor(len/2); i>=0; i--) {
        heapAjust(data, i, len);
    }
}
// 堆调整函数，即调整当前data为大根堆
function heapAjust(data, i, len) {
    var child = 2*i + 1;
    // 如果有孩子结点，默认情况是左孩子
    while(child <= len) {
        var temp = data[i];
        // 如果右孩子存在且其值大于左孩子的值，则将child指向右孩子
        if(child + 1 <= len && data[child] < data[child + 1]) {
            child = child + 1;
        }
        // 如果当前结点的值小于其孩子结点的值，则交换，直至循环结束
        if(data[i] < data[child]) {
            data[i] = data[child];
            data[child] = temp;
            i = child;
            child = 2*i + 1
        }else {
            break
        }
    }
}
// 排序
function heapSort(data) {
    var data = data.slice(0);
    if(!(data instanceof Array)) {
        return null;
    }
    if(data instanceof Array && data.length == 1) {
        return data;
    }
    // 将data数组改造为“堆”的结构
    buildHeap(data);

    var len = data.length;
    // 下面需要注意的时候参数的边界，参考文档里面程序中i的值是不对的
    for(var i=len-1; i>=0; i--) {
        swap(data, i, 0);
        heapAjust(data, 0, i-1);
    }
    return data;
}
const arr = [62, 88, 58, 47, 35, 73, 51, 99, 37, 93];
var newArr = heapSort(arr);
console.log(newArr);  // [35, 37, 47, 51, 58, 62, 73, 88, 93, 99]
复制代码

注意：很多博客中写了堆排序的JavaScript实现代码，有些文章中的程序存在参数边界不正确和数组中值的交换位置不合理等问题，本文中代码已经通过调试验证。

总结

这篇文章虽然字数不多，但是写作的过程是异常不顺畅的。因为要理解下面几个问题。

1. 什么是“堆”？
2. 怎么用程序构建“堆”？
3. 如果基于“堆”做排序？

想要搞明白上面三个问题还要先搞定数据结构中的“树”、“二叉树”以及其相应的特点，本文开头两篇文章可供阅读了解它们的相关知识。

话说回来，个人感觉用“堆排序”的方式对数组进行排序，着实有些浪费大脑。本着存在即有价值的理念，欢迎大家能发觉“堆排序”的真正用武之地，期待能够抛砖引玉。