堆排序是指利用堆这种数据结构对数据进行排序的算法。要了解堆排序，我们要先对堆进行一定的了解。
堆
堆是一种特殊的完全二叉树。在完全二叉树的基础上，堆还有以下特点：
堆的每个父节点都大于等于其所有子节点 这类堆被称为大堆
或者
堆的每个父节点都小于等于其所有子节点 这类堆被称为小堆
比如下面的二叉树就是一个小堆
?堆的向下调整算法
了解了堆的基本概念后，我们来了解如何将一个完全二叉树转变为堆。
首先，我们可以利用向下调整算法将一个左右子树都为堆（要得到小堆则两个子树都要是小堆，要得到大堆则两个子树都要是大堆）的完全二叉树转变为一个堆。
向下调整算法具体操作为：
如果要得到一个小堆，先将根节点与其两个子节点比较。如果根节点小于子节点，就将较小的子节点与根节点交换，并且继续向下进行这一操作。
但是，向下调整算法只能在左右子树都为堆的前提下进行。那么，怎么将一个不符合该要求的完全二叉树变为堆呢??
如何建立一个堆?
对于一个任何完全二叉树，当左子树或右子树不为堆时，我们可以先将其左子树与右子树按照向下调整算法转化为堆，这样就可以满足要求了，再利用向下调整算法这个完全二叉树转化为堆。
所以，我们从倒数第一个非叶子节点开始调整，直到调整到根节点，就可以把这个完全二叉树转化为堆了。
建堆代码如下
void down(int* arr,int father,int lastchild)//向下调整算法，此处以建小堆为例
{
int child = father * 2 + 1;//创建子节点
while (child<=lastchild)//当后面还有子节点时继续走
{
if (child + 1 <= lastchild && arr[child + 1] < arr[child])//找更小的子节点
{
child++;
}
if (arr[child] < arr[father])//比较父子节点
{
int tmp = arr[child];//交换父子节点
arr[child] = arr[father];
arr[father] = tmp;
father = child;//父子节点向下走
child = father * 2 + 1;
}
else
{
break;//父节点比子节点都大时退出循环
}
}
}
void heap(int* arr,int n)//建堆
{
int node = 0;//保存最后一个非叶子节点
for (node = (n - 1 - 1) / 2; node >= 0; node--)//从最后一个非叶子结点向前走到根节点
{
down(arr,node, n - 1);
}
}了解完了堆的基本概念与如何建堆,接下来我们来讲解堆排序算法?
堆排序
若要进行堆排序，我们需要一个已经排成堆的完全二叉树，这里我们以排升序为例讲解。
要排升序，我们需要先建立一个大堆，可能大家会认为，这里应该建立小堆，但是若建立小堆，我们第一个节点即根节点就是最小的节点，这样取走根节点后，只剩下左子树与右子树，而左子树与右子树没有绝对的关联性，所以每取走一个节点后继续排序后面的节点都需要重新建堆。
但是如果我们建立大堆，此时根节点就是最大的节点，我们将堆的最后一节点与根节点进行交换。
?
我们在每一次交换后，将堆的元素数量减1，这样我们之后的操作就不会影响到最后一个节点了。
这样，最大的数就移动到最后一位了，此时我们的左右子树依然是大堆，只需要对根节点进行向下调整，就可以得到一个新的大堆。之后，再重复上述的操作，直到节点固定下来，就完成了排升序。
?
?
?堆排序代码如下，其中向下调整算法与建堆代码参考上文
void heapsort(int* arr, int n)
{
heap(arr, n);//建堆
for (n = n - 1; n >= 1; n--)//每次循环堆大小减一，直到剩下最后一个节点停止循环
{
down(arr, 0, n);//对根节点进行向下调整算法调整位置
int tmp = arr[0];//交换首尾节点
arr[0] = arr[n];
arr[n] = tmp;
}
}?