堆排序

本文主要介绍堆的构造, 元素在堆中的上浮操作以及下沉操作，最后讲述基于这些操作的堆排序, 不对优先队列作介绍

堆是什么？

• 印象中的堆
  印象中的堆是这样的

其实数据结构中的堆也很相似，只是节点之间多了一些逻辑的关系。

• 数据结构中的堆

数据结构中的堆节点和节点间多了一些必要的逻辑关系， 方便我们遍历。堆中有顶点，每一个节点(图片中的块)一般都有两个子节点，当然最下的节点可能没有子节点。可以从顶向下一次编号，采用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抽出值调整堆
  给出如下排序过程。
  

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位置留一个哨兵项。