定义：

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

排序思想：

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

动图描述：

 

代码描述：

//该函数作用就是交换父子节点最大值void heapify(int tree[], int n, int i){    //序号i的左孩子    int c1 = 2 * i + 1;    //序号i的右孩子    int c2 = 2 * i + 2;    //假设序号i为最大值    int max = i;    //如果左孩子的值大于父亲的值    if (c1 < n && tree[c1] > tree[max])    {        max = c1;    }    //如果右孩子的值大于父亲的值    if (c2 < n && tree[c2] > tree[max])    {        max = c2;    }    //如果序号i不是最大值，所以进行交换    if (max != i)    {        int temp = tree[i];        tree[i] = tree[max];        tree[max] = temp;        heapify(tree, n, max);    }}//该函数作用就是建造一个树，使树中各个父节点的值大于子节点void build_heap(int tree[], int n){    //找到树中最后的叶节点的序号    int last_node = n - 1;    //找到该节点的父节点序号    int parent = (last_node - 1) / 2;    for (int i = parent; i >= 0; i--)        heapify(tree, n,i);}//对树进行排序，将根节点和树中序号最大的点进行交换，树中节点的数量减1，剩下的节点交换以此类推void heap_sort(int tree[], int n){    build_heap(tree, n);    for (int i = n - 1; i >= 0; i--)    {        int temp = tree[i];        tree[i] = tree[0];        tree[0] = temp;        heapify(tree, i, 0);    }}