堆排序
前言
本文主要介绍堆的构造, 元素在堆中的上浮操作以及下沉操作，最后讲述基于这些操作的堆排序, 不对优先队列作介绍。
一、堆是什么？
- 印象中的堆
印象中的堆是这样的
印象中的堆
其实数据结构中的堆也很相似，只是节点之间多了一些逻辑的关系。
- 数据结构中的堆
数据结构中的堆节点和节点间多了一些必要的逻辑关系， 方便我们遍历。堆中有顶点，每一个节点(图片中的块)一般都有两个子节点，当然最下的节点可能没有子节点。可以从顶向下一次编号，采用1开始。
数据结构中的堆
- 节点之间的序号关系
不难看出节点中的序号关系如下图
节点关系
当然从0开始编号关系也类似。
二、堆节点swim上浮
swim操作可以对堆中的任何节点进行操作， 比如函数写位swim(int k) k是要swim操作的节点序号。
节点关系
逻辑
比如Swim(5) 即 T, 就是T和它的上层父节点P比较。如果T大，T就和P交换, 一直和上边父节点比较， 比过了就向上交换，比不过就停下来， 这很像武林中的登塔闯关， 和一个一个的高手比较如果能打过就能继续向上(比不过的下去)，比不过就停下来。
节点关系
代码描述
swim(int k){
while(k>1 && less(k/2, k))
{
exch(k/2,k);
k = k/2;
}
}
代码中k = k/2 就利用了节点序号之间的关系。
三、堆的sink下沉操作
下沉节点
逻辑
sink(5),就是该元素和下边的元素比较， 如果比下边的小就交换(如果比两个都小就和两个钟大的那一个交换)，一直往下，找到两个都比他小的就停止。保证三个节点的有序， 子节点比父节点小的三角原则。
代码描述
void sink(int k){
while(2*k <= N){
int j = 2*k;
if(j < N && less(j, j+1)) j++;
if(!less(k, j)) break;
exch(k, j);
k = j;
}
}
代码中k = k/2 就利用了节点序号之间的关系。
四、利用sink使堆有序化
思路:sink一次可以让子节点有序化(子节点小于父节点)同理，依次sink，就可以使整个堆有序，堆有序是堆排序的前提。
排序示例
按照分析只需要执行:
- sink(5)
- sink(4)
- sink(3)
- sink(2)
- sink(1)
五、堆排序
经过上边的有序我们都已经知道什么是堆， 怎么让堆有序化，下面直接进入堆排序。
核心思想
1.取出最值
2.加入新的值
这种思想可以运用在优先队列上。
比如对数组 {40，70，20，60，50，10，10，30，80} 进行从小到大排序, 把最小值拿到最上边，最大值放后边。找出最大值，放数组后边， 对剩余数组构成的有序堆再尾节点和顶节点交换，下沉使其有序
思考：数组怎么转化为堆呢？一图就明白了。
-
1数组转为无序堆
数组转为无序堆结构
-
2堆有序化依次
-
3抽出值调整堆
给出如下排序过程。
1抽出最值->剩下的调整堆有序化
2抽出剩下的最值->剩下的调整堆有序化
3抽出剩下的最值->剩下的调整堆有序化
4重复使其全部有序
Code
int a[9] = {40, 70, 20, 60, 50, 10, 10, 30, 80};
int len = 9;
for (int i = len/2 - 1; i>=0; i--) {
sink(a, i, len);
}
//1.堆已经有序
printOutcome(a, N);
//2.重复交换顶底 再sink
while (len > 1) {
exchange(a, 0, --len);
sink(a, 0, len);
}
开始标号用1和0，有些许差异在代码上。但是1的话会给数组0位置留一个哨兵项。
