一、堆的概念

概念：堆作为一种数据结构是一种完全二叉树。所谓完全二叉树，可能有些书本有很晦涩难懂的概念。就我的理解可以将其理解为——二叉树在按层序遍历时在遇到第一个NULL指针即作为结尾的二叉树就可以称之为完全二叉树。

注意：这里说的堆并不是堆内存，堆内存是存储块状，大小不一的空闲链表。而堆数据结构则是树结构，并且是完全二叉树。

二、堆排序的概念

现在我们要利用完全二叉树的结构对堆进行排序。我们以一串整数为例。假设现在我们有一个数组a[10]={5,10,7,34,23,58,2,55,35,45}。

• 首先，从数组的角度来看，我们应当把这10个数从小到大地排起来：{2,5,7,10,23,34,35,45,55,58}。我们最后存储堆排序的数时，也采用数组的形式，只是我们要利用堆的数据结构来处理思路。
• 其次，我们当然可以把思路转移到堆的数据结构上。一开始我们初始化的时候要做n次赋值。也就是将a[0]放到根结点，而a[n]放在完全二叉树的最后一个叶子结点上。
• 接下来引入最大最小堆的概念。最大堆就是根结点拥有最大的数，而根结点的孩子结点也分别构成一个堆，以此类推直至最后一个结点。而最小堆自然就是根结点拥有最小的数了。我们堆排序，最终的目的就是将整个堆里的结点在层序遍历时由大到小（由小到大）按序号排列。

具体排序过程：

首先明确：按序号0~9来排列，如果我们现在处理第i个序号的结点的数，那么他的父结点序号就是(i-1)/2，它的孩子结点就为2i+1与2i+2。

让我们跟着代码来学习一下。

//main.cpp
#include<iostream>
using namespace std;
void MaxSort(int a[], int i, int n)
{
    int j = 2*i+1;//找到当前结点的左孩子
    int temp = a[i];//把当前结点的数赋给temp变量，后面会发现这个变量很有用
    while(j < n)//判断必须条件，大于或等于该结点都属于数组越界
    {
        if(j+1 <n && a[j] < a[j+1])//判断条件，第一个条件是判断是不是最后一个结点。
                                   //第二个判断条件是找出孩子结点最大的数方便与结点交换。
            ++j;//如果后面的大，那么交换的变成后面的孩子。
        if(temp > a[j])//因为我们是MaxSort所以如果父结点本身就大不用判断直接跳出循环。
            break;
        else
        {
            a[i] = a[j];//判断过程，把最大的孩子结点的数赋给父结点。并利用递归思想找出子节点的子节点。
            i = j;
            j = 2*i+1;
         }
    }
    a[i] = temp;//i已经成为了孩子结点的下标，赋值temp，也就是原本父结点的值，达成交换。
}
 
 //堆排序
void HeapSort(int a[], int n)
{
    for(int i= n/2-1;i>=0;i--)//从最后一个结点的父结点开始“向前遍历”。
        MaxSort(a,i,n);
    for(int i=n-1;i>=1;i--)
    {
        //swap(a[i],a[0]);
        MaxSort(a,0,i);
    }//逆序
}
int main()
{
    int a[10] = {5,10,7,34,23,58,2,55,35,45};
    HeapSort(a,10);
    for (int i=0;i<10;i++)
        cout << a[i] << " ";
    return 0;
}

现在让我们跟着代码逐次来分析一下。算法交代的东西都写在代码注释上了。后面主要写写这么写的思路，图片有点大。。。
1）首先，我们设置数组a[10]，并按层序遍历的顺序排列好。

初始状态.png

2）第一次排序，最后一个结点的父结点只有一个孩子。并且父结点要小，利用排序，交换到上面。

第一次排序.png

3）第二次排序，先判断两个孩子结点谁大，再判断父结点与最大的孩子结点哪个数更大。判断完后作出交换，思路与第一次排序相同。

第二次排序.png

4）第三次排序，不上图了，思路一样，把7和58交换。
5）第四次排序，判断的是a[1]=10这个点。根据代码，a[i]被赋予了55这个值，但同时我们注意——为什么代码在上层结点赋值完不直接把较小的那个值赋值到最下面？原因就在于我们可以通过递归的思路一直将一条子树的顺序遍历完。当j赋值给i以后，i=3，而2i+1=7并没有越界，那么根据循环条件j<n，我们还要继续判断下面的子树的情况，从而构成递归。我们继续判断a[3]=10的子树a[7],a[8]。发现a[3]依旧小，那么继续交换，完成一条子树上的完整排序。

第四次排序.png

那么到这里，所有排序的出现可能都经历过了。剩下的就是循环重复直到Heapsort函数第一个外圈循环结束。结束后的排序是这样的：

第一轮排序结束.png

我们发现，这并不是我们想要的理想堆。它只是保证了父结点永远比子节点大，但是却还没有处理兄弟结点的问题。

因此我们需要第二个循环的帮助。第二个循环主要起这个作用：
1）不管第一轮排序结束是不是有序数组，它的根结点始终是最大的。因此第一轮循环结束有两个性质：a.找出最大结点放于根结点 b.使得父结点永远比子结点大。
2）因此我们上来先把a[9]与a[0]互换，这样a[9]就成了堆的最大值。再将前n-1项进行第一次的循环找出最大值并放置于根结点。并且形参i一直传递的是0，也就是说我们排序的永远是根结点。
根据性质a：每一次循环我们都将最大值放在了二叉树的根结点。
根据性质b：我们第一次循环后，父结点永远比子结点大。那么就可以保证根结点的孩子结点的其中之一必定是除根结点以外的最大值。因此无论我们从a[i]换到a[9]的值如何移动，第一次交换到根结点的那个值必定是最大值。（这句话好好理解下）
3）重复以上步骤，每次执行第一轮循环的数减一（为了保证移动到最后的那些由小到大的有序数字的顺序不变）数最大的值被一直移动到根结点然后swap到末端。最终堆排序就可以完成由小到大的排序啦。

最终输出结果：

输出结果.png