前面我们已经讲过二叉堆是啥了，然后也晓得最大堆和最小堆的实现。（不晓得的同学，传送门走起：//www.greatytc.com/p/d79e39430cd2）
一般数组排序，我们都是默认按从小到大排，所以这要用到的最大堆（如果是按从大到小，那么同理就用最小堆实现）。所以后面说到堆都是特指最大堆哈。
先看下最大堆的实现：
/*
二叉堆的最大堆代码实现
*/
// 根据子节点下标的奇偶性，来获取对应父节点的下标
function getParentIndex(childIndex) {
let parentIndex = 0;
if(childIndex % 2 === 0) {
parentIndex = (childIndex - 2) / 2 // 如果是右节点，父节点的下标
}else{
parentIndex = (childIndex - 1) / 2 // 如果是左节点，父节点的下标
}
return parentIndex;
}
// 最大堆上浮(一般对应插入操作)
function upAdjust(arr) {
let childIndex = arr.length -1; // 初始子节点的下标
parentIndex = getParentIndex(childIndex)
let temp = arr[childIndex] // 子节点值
while((childIndex > 0) && (temp > arr[parentIndex])) {
arr[childIndex] = arr[parentIndex]
childIndex = parentIndex
// 根据子节点下标的奇偶性，来获取对应父节点的下标
parentIndex = getParentIndex(childIndex)
}
arr[childIndex] = temp
return arr;
}
const testArr1 = upAdjust([4,2,9,1,7,8,36])
console.log(testArr1); // [ 36, 2, 4, 1, 7, 8, 9 ]
/**
* @description 二叉堆下沉（最大堆）
* @param arr: 待调整的二叉堆
* @param parentIndex: 要下沉的父节点位置
* @param length: 堆的有效长度，也就是要做下沉的区间范围
* @return arr: 调整后的二叉堆数组
*/
function downAdjust(arr, parentIndex, length) {
// const len = arr.length;
// 保存父节点的值，用于最后赋值
let temp = arr[parentIndex]
// 左节点下标值
let childIndex = parentIndex * 2 + 1;
// 如果存在左孩子节点
while(childIndex < length) {
// 检测是否存在右节点，且右节点比左节点大点，则取右节点下标值；否则还是使用左节点下标
if(childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
childIndex++;
}
// 如果父节点值比左右节点中最大的节点值都要大，那么结束
if(temp > arr[childIndex]) break;
// 否则，将爷节点与最大子节点值交换
arr[parentIndex] = arr[childIndex]
parentIndex = childIndex
childIndex = parentIndex * 2 + 1
}
arr[parentIndex] = temp
return arr;
}
const testArr2 = downAdjust([4,2,9,36,7,8,1,3], 0, 8)
console.log(testArr2); // [ 9, 2, 8, 36, 7, 4, 1, 3 ]
/**
* @description 构造二叉堆，将无序的完全二叉树转换成一个二叉堆（最小堆）
* @param arr: 待调整的完全二叉树数组
* @return arr: 调整后的二叉堆
*/
function buildMaxHeap(arr) {
let childIndex = arr.length - 1
let parentInddex = getParentIndex(childIndex)
for(let i = parentInddex; i >= 0; i--) {
downAdjust(arr, i, arr.length)
}
return arr;
}
const testArr3 = buildMaxHeap([4,2,9,36,7,8,1,3])
console.log("testArr3:", testArr3); // [ 36, 7, 9, 3, 4, 8, 1, 2 ]
堆的下沉操就是把要下沉的元素（后面记做parent了），依次对比它的左右子节点，记录子节点中最大值 childMax = max(左子节点，右子节点)，如果子节点max都比parent小，则结束；如果childMax > parent，则两者交换位置。然后将这个parent继续做下沉操作，直至子节点中没有比parent大的值或没有子节点为止。
其实堆下沉，我们往往是用来用删除操作。
比如：这个最大堆[ 36, 7, 9, 3, 4, 8, 1, 2 ]，我们如果要删除36，就是把2和36的位置交换，然后删除36，然后对2进行下沉,最后得到[ 9, 7, 8, 3, 4, 2, 1 ]，会发现9是下个堆的最大值，也就是原堆的第二大值。
利用这个特性，我们每次将删除的堆顶，都不做删除操作（假删除操作），而是丢到除了有序区间的最后一位。我们就可以简单地实现堆排序了：
- 初始堆[ 36, 7, 9, 3, 4, 8, 1, 2 ]，第1次执行删除36，最后一位与36交换得到[ 2, 7, 9, 3, 4, 8, 1, 36 ]，然后对2进行下沉操作时，忽略最后一个节点，这样就可以得到[ 9, 7, 8, 3, 4, 2, 1, 36 ],执行第1次后就可以把最大值放在最后了
- 第2次执行删除9，和倒数第二位1换位置，[ 1, 7, 8, 3, 4, 2, 9, 36 ]，然后对1进行下沉操作，忽略后二位节点，这样就可以得到[ 8, 7, 2, 3, 4, 1, 9, 36 ]，执行第2次后就可以得到最后两位的有序区间了
- 第3次执行删除8，和倒数第三位1交换位置[ 1, 7, 2, 3, 4, 8, 9, 36 ]，然后对1进行下沉操作，忽略后三位节点，这样就可以得到[ 7, 4, 2, 3, 1, 8, 9, 36 ]
- 第4次执行删除7,和倒数第4位交换位置[ 1, 4, 2, 3, 7, 8, 9, 36 ]，然后对1进行下沉操作，忽略后4四位有序区间，这样就可以得到[ 4, 3, 2, 1, 7, 8, 9, 36 ]
- 第5次执行删除4,和倒数第5位交换位置[ 1, 3, 2, 4, 7, 8, 9, 36 ]，然后对1进行下沉操作，忽略后5四位有序区间，这样就可以得到[ 3, 1, 2, 4, 7, 8, 9, 36 ]
- 第6次执行删除3,和倒数第6位交换位置[ 2, 1, 3, 4, 7, 8, 9, 36 ]，然后对2进行下沉操作，忽略后6四位有序区间，这样就可以得到[ 1, 2, 3, 4, 7, 8, 9, 36 ]，这时就剩下1个1是堆顶了，没有要比较的队列了，因为右边的已经全是有序队列了，所以此时结束后，就能得到排序结果了
所以只要在最大堆的基础上，做次遍历删除操作就好了：
/*
* 堆排序实现
*/
function heapSort(arr) {
// 将无序数组转换成为最大堆
let heap = buildMaxHeap(arr)
// 然后依次对堆进行删除操作
for(let i = heap.length -1; i > 0; i--) {
// 每次将堆顶假删除，放最后
[ heap[0], heap[i] ] = [ heap[i], heap[0] ]
// 然后对新的堆顶做下沉操作，构成新的最大堆
downAdjust(heap, 0, i)
}
return heap;
}
let heap = heapSort([7, 36, 9, 3, 4, 8, 1, 2])
console.log('heap:', heap); // [ 1, 2, 3, 4, 7, 8, 9, 36 ]
这时候，我们来分析下它的时间复杂度和空间复杂度了：
- 空间复杂度，基本上没有创建新地址空间,所以是O(1)
- 时间复杂度：
- 把无序数组转换成堆的复杂度是O(n)
- 下沉操作是O(logn)，遍历操作是O(n)
所以总的是O(n + nlogn),相当于O(n(1+logn)),然后常量可以忽略，所以平均下来就约等于O(nlogn)了
排序算法系列文章传送门(未完，持续更新中)：
排序算法-1（javascript） 冒泡、选择、插入、希尔排序的实现
排序算法-2（javascript） 快速排序的实现
排序算法-3（javascript） 堆排序的实现
排序算法-4（javascript） 归并排序的实现
