二叉堆的特征：

1. 最大堆的堆顶是整个堆中最大的元素

2. 最小堆的堆顶是整个堆中最小的元素

以最大堆为例，如果删除一个最大的堆顶(并不是真正意义上的删除，而是和末尾节点交换位置)，经过自我调整，第二大元素就会被交换上来，成为最大堆的新堆顶

由于二叉堆的这个特性，每一次删除旧的堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点，那么只要反复删除堆顶，反复调整二叉堆，所得到的的集合就会成为一个有序的集合，过程如下：

删除节点 9，节点 8 成为新的堆顶

删除节点 8，节点 7 成为新的堆顶

删除节点 7，节点 6 成为新的堆顶

删除节点 6，节点 5 成为新的堆顶

删除节点 5，节点 4 成为新的堆顶

删除节点 4，节点 3 成为新的堆顶

删除节点 3，节点 2 成为新的堆顶

到此为止，原本的最大二叉堆已经变成了一个从小到大的有序集合，

由此，可以归纳出堆排序算法的步骤：

1. 把无序数组构建成为二叉堆，需要升序，则构建最大二叉堆，需要降序则构建最小二叉堆

2. 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶

代码

1  
2    /**
3     * @param {Array<number>} arr 待调整的堆
4     * @param {number} parentIndex 要下沉的父节点
5     * @param {number} length 堆的有效大小
6     * @description 下沉调整 最大堆
7     */
8    function downAdjust(arr: Array<number>, parentIndex: number, length:number) {
9        // temp 保存父节点的值，用作最后赋值
10        let temp = arr[parentIndex];
11        // 左子节点下标
12        let childrenIndex = parentIndex * 2 + 1;
13        while(childrenIndex < length) {
14            // 如果存在右节点，且右节点比左节点大 则定位到右节点
15            if(childrenIndex + 1 < length &amp;&amp; arr[childrenIndex + 1] > arr[childrenIndex]) {
16                childrenIndex = childrenIndex + 1;
17            }
18            // 如果父节点大于等于最大子节点，则直接break
19            if(temp >= arr[childrenIndex]) {
20                break
21            }
22            // 单向赋值
23            arr[parentIndex] = arr[childrenIndex];
24            parentIndex = childrenIndex
25            childrenIndex = childrenIndex * 2 + 1
26        }
27        arr[parentIndex] = temp;
28    }
29    
30    
31    
32    /**
33     * @param {Array<number>} arr 待调整的堆
34     * @description 堆排序 升序
35     */
36    function heapSort(arr:Array<number>) {
37        // 1. 把无序数组构建为最大堆
38        for (let index = arr.length - 2; index >= 0; index--) {
39            downAdjust(arr, index, arr.length - 1)
40        }
41    
42    
43        console.log('最大堆: %j', arr)
44    
45    
46        // 2. 循环删除堆顶元素，移动到数组尾部，调整堆，产生新的堆顶
47        for (let index = arr.length - 1; index >= 0; index--) {
48            // 最后一个元素和 堆顶交换
49            let temp = arr[0];
50            arr[0] = arr[index];
51            arr[index] = temp;
52            // 下沉调整最大堆 
53            downAdjust(arr, 0, index)
54            // index 的值 为堆的有效长度 这里很巧妙
55        }
56    
57    
58    }
59    
60    
61    function main() {
62        let arr = [1, 3, 2, 6, 5, 7, 8, 9, 10, 0];
63        heapSort(arr);
64        console.log(arr)
65    }
66    main()
67

小结

时间复杂度

二叉堆的节点下沉调整(downAdjust方法)是堆排序算法的基础，它的时间复杂度为O(logn)

第一步把无序数组构建为二叉堆，这一步时间复杂度为O(n)

第二步进行 n-1 次循环，每次循环调用下沉方法，所以步骤 2 的规模为 (n-1)*logn

两个步骤是并列关系，所以整体时间复杂度为O(nlogn)

快速排序和堆排序对比

相同点：

堆排序和快速排序的平均时间复杂度都是O(nlogn)，并且都是不稳定排序

不同点：

1. 快速排序的最坏时间复杂度为O(n2)，而堆排序则稳定在O(nlogn)

2. 快速排序的递归和非递归实现 空间复杂度 都是O(logn)，而堆排序的空间复杂度为O(1)

摘要总结自: 漫画算法 小灰的算法之旅