- A+
什么是堆排序？
是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点
在看本文之前请先了解以下概念
完全二叉树：除了最后一层之外的其他每一层都被完全填充，每一层从左到右的填充数据，不能空缺（只是类似这个结构，所以本文不会用到这个知识点）
堆：分为大顶堆和小顶堆两种
大顶堆（小顶堆）：可分为有序区和无序区，初始全部为无序区
执行的步骤是如何进行的？
-
无非就是将一个无序数组转化为大顶堆（小顶堆）
-
将堆顶的值和无序数组末尾值交换位置
-
根据堆的性质进行调整，成为大顶堆（小顶堆）
-
然后又继续 1~3 的步骤，反反复复直到无序区没有值为止
这个时候肯定会有人问，怎么区别有序区和无序区？什么是大顶堆（小顶堆）？以及大顶堆（小顶堆）是如何调整出来的？
如何辨别有序区和无序区？
循环结束后应该是这样的，没有无序区了
上面的大顶堆（小顶堆）实际在存储在数组中是这样的
现在应该知道有序区和无序区如何分辨了吧，以及大顶堆是如何在数组中进行存储的
什么是大顶堆（小顶堆）？
通过上图应该都能看出来大顶堆和小顶堆的区别了吧。
大顶堆：每个结点的值都大于或等于其左右孩子结点的值（大到小排列）
小顶堆：每个结点的值都小于或等于其左右孩子结点的值（小到大排列）
大顶堆（小顶堆）是如何调整出来的？
也是本文中最难理解的地方，下面简单描述一下主要的步骤：
目标：将无序数组(R1,R2....Rn)构建成大顶堆，即完成任务
-
初始时，此堆的所有值都是属于无序区
-
将堆顶元素 R[1]与无序区中最后一个元素 R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn)
-
由于交换后新的堆顶 R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆
-
然后再次将 R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到无序区的元素个数 0，则整个排序过程完成
总结
-
其实主要的操作就是构造初始堆和调整堆。
-
每次调整都是从父节点（i - 1）/ 2、左孩子节点（2 _ i + 1）、右孩子节点（2 _ i + 2）三者中选择最大者跟父节点进行交换位置
堆排序过程
参考资料
神级基础排序——堆排序
值得收藏的十大经典排序算法
漫画：什么是堆排序？
堆排序（大根堆）
文章的内容/灵感都从下方内容中借鉴
-
【持续维护/更新 500+前端面试题/笔记】https://github.com/noxussj/Interview-Questions/issues
-
【大数据可视化图表插件】https://www.npmjs.com/package/ns-echarts
-
【利用 THREE.JS 实现 3D 城市建模（珠海市）】https://3d.noxussj.top/
