堆排序（Heapsort）的基础
定义：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
我们需要了解什么叫堆
定义
n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n/2），当然，这是小根堆，大根堆则换成>=号。//k(i）相当于二叉树的非叶子结点，K(2i）则是左子节点，k(2i+1）是右子节点
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。
来个例子说明
【例】关键字序列（10，15，56，25，30，70）和（70，56，30，25，15，10）分别满足堆性质（1）和（2），故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。
小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。
大根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。
注意：①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆（Binary Heap），类似地可定义k叉堆。
来张图表示一下：
堆的高度
堆可以被看成是一棵树，结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目；定义堆的高度为树根的高度。我们将看到，堆结构上的一些基本操作的运行时间至多是与树的高度成正比，为O（lgn）。
算法描述
<1>.将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
<2>.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
<3>.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
代码实现
```
/**
* 对数组中的前n项整理成堆
* @param array
* @param n
*/
function refreshHeap(array, n){
if(array.length<n)n = array.length;
//array[n/2-1]表示的是最后一个有子节点的节点
for(let i=Math.floor(n/2)-1;i>=0;i--){
//对于有子节点的节点i，2*i+1表示的是其第一个子节点，即左子节点
//这个while是判断当前节点与其子节点是否需要调整
while(2*i+1<n){
let j = 2*i+1;
//如果节点j不是其父节点的唯一子节点，也就是说如果存在右子节点
if(j+1<n){
//如果右子节点大于左子节点，则使j指向右边（总之要找到最大的子接点）
if(array[j]<a[j+1]){
j++;
}
}
//如果最大子节点大于其父节点，则交换
if(a[i]<a[j]){
let tmp = a[i];
a[i] = a[j];
a[j] = tmp;
//交换之后整个堆被破坏，需要重新调整，故令i=j
//这个调整表示的是从j节点开始判断堆是否需要调整
//比如交换j、i节点后，结果j的子节点又大于j了，那么就需要重新调整
i = j;
}else{
break;
}
}
}
return array;
}
function heapSort(array, n){
if(array.length<n)n = array.length;
while(n>0){
//刷新堆之后，将array[0]（最大值）与最后一个子节点交换
//然后重新刷新堆(不包括最后那些排好序的节点了)
refreshHeap(array, n--);
let tmp = array[n];
array[n] = array[0];
array[0] = tmp;
}
return array;
}
var a = [16,7,3,20,17,8];
console.log(a); // [16, 7, 3, 20, 17, 8]
heapSort(a,a.length);
console.log(a); // [3, 7, 8, 16, 17, 20]
```
时间复杂度：T(n) = O(nlogn)
空间复杂度：S(n) = O(1)
稳定性：不稳定
排序方式：内排序
动图展示
参考文档：
JavaScript数据结构之 堆排序
十大经典排序算法
堆排序
