一、基础知识

1. 满二叉树每层节点数为2⁰、2¹、2²……2^d-1，总节点数为∑2ⁱ=2^d-1=n，d=log₂(n+1)；完全二叉树层序遍历节点顺序和满二叉树对应位置节点顺序一样，即节点之间没有空白节点，其深度为|log₂n|+1（|log₂n|表示不大于log₂n的最大整数）；
2. 堆，分为大顶堆（大堆）和小顶堆（小堆），是顺序存储的完全二叉树，并且满足以下特性之一：
   • 任意非终端结点关键字不小于左右子结点（大堆）k_i >= k_2i+1并且k_i>=k_2i+2 其中，0 <= i <= (n-1)/2，n是数组元素个数
   • 任意非终端结点关键字不大于左右子结点（小堆）k_i <= k_2i+1并且k_i<=k_2i+2 其中，0 <= i <= (n-1)/2，n是数组元素个数
3. 假设父节点索引为i，所处层级为d，其上层以前总节点数为2^d-1，在本层处于第k个元素，则i=2^d-1+k-1=2^d+k-2；左子节点left所处层级为d+1,其上层以前总节点数为2^(d+1)-1，在本层处于第2*k-1个元素,则left=2^(d+1)-1+2*k-1-1=2*(2^d+k-2)+1=2*i+1，右子节点right=left+1=2*i+2；
4. 最后一个非叶子节点，如果节点序号为i，在它的左孩子序号为2*i+1，右孩子序号为2*i+2；
   • 只有左孩子，左孩子的序号为n-1，则n-1=2*i+1，推出i=n/2-1；
   • 左孩子的序号为n-2，在n-2=2*i+1，推出i=(n-1)/2-1；右孩子的序号为n-1，则n-1=2*i+2，推出i=(n-1)/2-1；

二、原理

       ☆思想：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质，利用每个结点和其子结点的相对大小保存排序结果，从而实现快速调整堆和输出堆顶结点；堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

       ☆过程：以递增为例，用数组表示，长度为n，层序遍历堆，把节点值顺序放入数组，堆顶在数组中索引最小，最后一个叶子节点在数组最后；排序主要有三个过程：

1. 创建堆，从下往上构建大顶堆，即找到最后一个非叶子节点，把它作为子树的根节点，调整子树为大顶堆；依次往前调整所有非叶子节点，直到堆顶；
2. 把堆首（最大值）和堆尾互换；
3. 把堆从后缩小 1，从堆顶开始从上往下调整，目的是把新的堆顶元素调整到相应位置；
4. 重复第2和3步，直到堆的尺寸为 1；

三、实现代码

      JavaScript 代码实现

function HeapSort(arr) {
    //数组长度
    var n;
    n = arr.length;
    //创建堆
    CreateHeap(arr);

    //每次把堆的最大值交换到堆的最后一个节点，堆的长度相应递减
    for (var i = n - 1; i > 0; i--) {
        swap(arr, i, 0);
        //每次从堆顶开始从上往下调整
        adjustHeapToDown(arr, 0, i);
    }
    return arr;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function CreateHeap(arr) {
    //数组长度
    var n = arr.length;
    //最后一个中间节点索引
    var index = Math.floor(n / 2 - 1);
    //从下往上构建大顶堆
    for (var i = index; i >= 0; i--) {
        //调整数组索引i对应子树，数组长度限制为n
        adjustHeapToDown(arr, i, n);
    }
}

function adjustHeapToDown(arr, index, len) {
    //调整数组索引index对应子树，数组长度限制为len
    var j, maxChildNodePos;
    j = index;
    while (j <= len / 2 - 1) {
        //找出子节点中较大者索引
        maxChildNodePos = getMaxChildIndex(arr.slice(0, len), j);
        //比较中间节点和其子节点  
        if (arr[j] < arr[maxChildNodePos]) {
            swap(arr, j, maxChildNodePos);
        }
        //把子节点作为起点 
        j = maxChildNodePos;
    }
}

//找出较大子节点的索引
function getMaxChildIndex(arr, i) {
    //超出最后一个中间节点
    if (i > arr.length / 2 - 1) return;
    //没有子节点
    if (!arr[2 * i + 1] && !arr[2 * i + 2]) return;
    //只有左子节点
    if (arr[2 * i + 1] && !arr[2 * i + 2]) return 2 * i + 1;
    //具有左右子节点
    if (arr[2 * i + 1] > arr[2 * i + 2]) {
        return 2 * i + 1;
    } else {
        return 2 * i + 2;
    }
}

四、优化

       无；

五、复杂度

      堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度最好和最坏情况下都是O(nlogn)级；

      本排序需要一个辅助变量，所占空间是常数与n无关；

      相同元素在堆中位置不确定，会交换，本排序不稳定。

 参考资料：

• 菜鸟教程
• https://www.cnblogs.com/l199616j/p/10741093.html
• 《大话数据结构》2011年清华大学出版社   作者程杰