什么是堆排序？

开门见山，本文讲述堆排序。

就我自身对于排序的了解来看，其实堆排序是诸多排序中最难写的，光是理解起来都有点费劲，本文旨在于用通俗易懂的话，把堆排序娓娓道来。

下面，开始！

1：堆

毫无疑问，排序两个字没必要去死磕，这里的重点，在于排序的方式，堆排序，就是以堆的形式去排序，毫无疑问，了解堆很重要。

那么，什么是堆呢？

这里，必须引入一个完全二叉树的概念，然后过渡到堆的概念。

上图，就是一个完全二叉树，其特点在于：

1. 从作为第一层的根开始，除了最后一层之外，第N层的元素个数都必须是2的N次方；第一层2个元素，第二层4个，第三层8个，以此类推。
2. 而最后一行的元素，都要紧贴在左边，换句话说，每一行的元素都从最左边开始安放，两个元素之间不能有空闲，具备了这两个特点的树，就是一棵完全二叉树。

那么，完全二叉树与堆有什么关系呢？

我们假设有一棵完全二叉树，在满足作为完全二叉树的基础上，对于任意一个拥有父节点的子节点，其数值均不小于父节点的值；这样层层递推，就是根节点的值最小，这样的树，称为小根堆。

同理，又有一棵完全二叉树，对于任意一个子节点来说，均不大于其父节点的值，如此递推，就是根节点的值是最大的，这样的数，称为大根堆。

如上图，左边就是大根堆；右边则是小根堆，这里必须要注意一点，只要求子节点与父节点的关系，两个节点的大小关系与其左右位置没有任何关系。

明确下大根堆，小根堆的概念，继续说堆排序。

现在对于堆排序来说，我们先要做的是，把待排序的一堆无序的数，整理成一个大根堆，或者小根堆，下面讨论以大根堆为例子。

给定一个列表array=[16,7,3,20,17,8]，对其进行堆排序（使用大根堆）。

接下来内容是转载部分，自己绘图功底太差：其中绿色部分为自己的注解。

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

　　a.假设给定无序序列结构如下

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

此处必须注意，我们把6和9比较交换之后，必须考量9这个节点对于其子节点会不会产生任何影响？因为其是叶子节点，所以不加考虑；但是，一定要熟练这种思维，写代码的时候就比较容易理解为什么会出现一次非常重要的交换了。

4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

在真正代码的实现中，这时候4和9交换过后，必须考虑9所在的这个节点位置，因为其上的值变了，必须判断对其的两个子节点是否造成了影响，这么说不合适，实际上就是判断其作为根节点的那棵子树，是否还满足大根堆的原则，每一次交换，都必须要循环把子树部分判别清楚。

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

牢记上面说的规则，每次交换都要把改变了的那个节点所在的树重新判定一下，这里就用上了，4和9交换了，变动了的那棵子树就必须重新调整，一直调整到符合大根堆的规则为截。

此时，我们就将一个无序序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

这里，必须说明一下，所谓的交换，实际上就是把最大值从树里面拿掉了，剩下参与到排序的树，其实只有总结点的个数减去拿掉的节点个数了。所以图中用的是虚线。

b.重新调整结构，使其继续满足堆定义

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

下面，附上我的代码，也是从文末链接中模仿过来的，但是亲自敲过一遍，印象深刻。

#include <iostream>


void swap(int arr[], int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

void adjustHeap(int data[], int len, int index)
{
    //int temp =data[index];

    //start from its left child
    for(int k = 2*index+1; k < len; k = 2*k+1)
    {
        //If the right child is larger than the left child, then pick the right one
        if((k+1 < len) && (data[k+1] > data[k]))
            k++;

        if(data[k] > data[index])
        {
            //swap them
            swap(data, index, k);

            index = k;
        }
        else
            break;
    }
}

void heapSort(int data[], int len)
{
    if((len <= 0))
        return;

    //start with first non-leave node
    for(int i = len/2-1; i>=0; i--)
        adjustHeap(data, len, i);

    for(int j = len -1; j > 0; j--)
    {
        //swap root node with last node
        swap(data, 0, j);
        
        //Start adjust from the root node
        adjustHeap(data, j, 0);
    }
}

int main() {

    int a[10] = {1,5,4,3,7,6,9,10,8,2};
    heapSort(a, 10);

    for(int i = 0; i < 10; i++)
        cout << a[i] << endl;

    return 0;
}