本文共 1907 字，大约阅读时间需要 6 分钟。

堆

definition：

堆是具有下列性质的完全二叉树（以大顶堆为例）： 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。

如果按层序遍历的方式给结点从1开始编号，则结点之间有如下关系（共n个结点）：

k[i]>=k[2i] ，k[i]>=k[2i+1] 1<=i<=n/2

堆排序算法

基本思想：

1.将待排序的序列构成一个大顶堆。此时，整个序列的最大值就是堆的根结点。 2.将根结点与堆数组的末尾元素交换，此时末尾元素就是最大值。 3.然后将剩余的n-1个序列重新调整为一个大顶堆，这样就可以得到次大值。如此反复执行，最终就可以得到一个有序序列。

难点：如何将一个序列调整为一个大顶堆。

！！！核心思路：调整的顺序是从下往上、从右到左，将每个非叶子结点作为根结点，将其和其子树调整成大顶堆。

调整函数HeapAdjust如下：

void HeapAdjust(int* a, int i, int num) {   	int temp = a[i];//temp最终赋给a[final]，fianl的值要等下面的for循环结束才知道	int final = i;	for (int j = 2 * i; j <= num; j *= 2)	{   		if (j != num&&a[j + 1] > a[j])			j++;//j记录较大的下标		if (temp > a[j])			break;		else		{   			a[i] = a[j];			i = j;			final = j;		}	}	a[final] = temp;}

为了说明调整函数的原理，给出一个二叉树如下图，我们需要把它调整为一个大顶堆：

此时a={0,50,70,90,60,10,40,80,30,20}，共有9个结点，因此需要依次对4个（9/2=4）非叶子结点（结点4、结点3、结点2、结点1）进行调整。 1.发现结点4及其子树已经构成了大顶堆，不需要调整； 2.发现结点3及其子树已经构成了大顶堆，不需要调整； 3.发现结点2及其子树已经构成了大顶堆，不需要调整； 4.结点1是需要进行调整的，所以执行HeapAdjust(a,1,num);，流程如下图所示：

下面给出一个完整的例子和代码：

#include
   
    using namespace std;void HeapSort(int* a, int length);void HeapAdjust(int* a, int i, int length);void swap(int* a, int i, int j){   	int temp = a[i];	a[i] = a[j];	a[j] = temp;}#define Num 9int main() {   	int a[Num + 1] = {    0,50,10,90,30,70,40,80,60,20 };	int num = Num;	HeapSort(a, num);	for (int i = 1; i <= num; i++)		cout << a[i] << endl;	system("pause");	return 0;}void HeapSort(int* a, int num) {   	for (int i = num / 2; i > 0; i--)//第一个循环：将数组a初始化为一个大顶堆		HeapAdjust(a, i, num);	for (int i = num; i > 1; i--)//第二个循环：将大顶堆的根结点元素与大顶堆的最后一个结点元素交换，并且再重新调整新的大顶堆（此时注意新的大顶堆的总结点个数要减1）	{   		swap(a, 1, i);		HeapAdjust(a, 1, i - 1);	}}void HeapAdjust(int* a, int i, int num) {   	int temp = a[i];//temp最终赋给a[final]，fianl的值要等下面的for循环结束才知道	int final = i;	for (int j = 2 * i; j <= num; j *= 2)	{   		if (j != num&&a[j + 1] > a[j])			j++;//j记录较大的下标		if (temp > a[j])			break;		else		{   			a[i] = a[j];			i = j;			final = j;		}	}	a[final] = temp;}