排序算法6——堆排序

【堆排序】

利用堆排序算法思想，对元素序列67，48，23，81，38，19，52，40进行从小到大排序。

【堆的定义】

堆排序是简单选择排序算法的一种改进。堆排序利用二叉树的性质对元素进行排序，将完全二叉树从上到下、从左到右依次编号，如果每一个双亲结点元素值大（小）于等于孩子结点元素值，则根据编号构成的元素序列就是大（小）顶堆。

假设有n元素：k_{1},k_{2},...,k_{n},如果满足以下关系：

或

其中小标1，2，...,n分别表示第1，2，...,n个元素，i=1,2,...,(向下取整)。则称这样的元素序列为小顶堆或大顶堆。

例如，元素序列89，77，65，62，32，55，60，48和18，37，29，48，50，43，33，69，77，60都是堆，相应的完全二叉树如下图所示：

在大顶堆中根结点对应元素值最大；在小顶堆中，根结点对应元素值最小。

【算法思想】
假设一个大顶堆中有n个元素，如果将堆中的根结点元素输出之后再将剩下的n-1个元素重新建立一个新堆，并将根结点元素输出，然后将剩下的n-2个元素重新建立成堆，重复执行上述过程，直到堆中没有元素为止。输出的元素就是一个有序的序列，这样的排序方法就是堆排序。

因此堆排序可以分为两个过程：床创建堆和调整堆。

1.创建堆

假设待排序元素有n个，依次存放在数组a中。第1个元素a[1]表示二叉树的根结点，剩下的元素a[2...n]依次与完全二叉树中的编号一一对应。例如，a[1]的左孩子结点元素存放在a[2]中，右孩子结点元素存放在a[3]，a[i]的左孩子结点元素存放在a[2*i]中，右孩子结点元素存放在a[2*i+1]。

如果是大顶堆，则有a[i]≥a[2*i]且a[i]≥[2*i+1] (i=1,2,...,)(向下取整)。如果是小顶堆，则有a[i]≤a[2*i]且a[i]≤[2*i+1] (i=1,2,...,$\lfloor n/2 \rfloor$)(向下取整)。

建立一个大顶堆就是将一个无序的元素序列构建为一个满足条件a[i]≥a[2*i]且a[i]≥[2*i+1] (i=1,2,...,$\lfloor n/2 \rfloor$)(向下取整)的元素序列。

建立大顶堆的算法思想：从位于元素序列中的最后一个非叶子结点（即第个元素）开始，逐层比较并调整元素的位置使其满足条件a[i]≥a[2*i]且a[i]≥[2*i+1]，直到根结点为止。具体方法如下：假设当前结点的序号为i，则当前元素为a[i]，其左右孩子结点元素分别为a[2*i]和a[2*i+1]。将a[2*i]和a[2*i+1]较大者与a[i]比较，如果孩子结点元素值大于当前结点元素值，则交换两者；否则不进行交换。逐层向上执行此操作，直到根结点，这样就建立了一个大顶顶堆。建立小顶堆的算法与创建大顶堆类似。

例如，给定一组元素序列27，58，42，53，42.，69，50，62，建立大顶堆的过程如图所示。

从图中可以看出，建立后的大顶堆中的孩子结点元素值都小于等于双亲结点元素值，其中，根结点的元素值69是最大的元素。创建后的堆的元素序列为：69，62，50，58，42.，42，27，53。

2.调整堆

其实，调整堆也是重新建立堆的过程。除了堆顶元素外，剩下的元素本省就具有a[i]≥a[2*i]且a[i]≥[2*i+1] (i=1,2,...,)(向下取整)的性质，即元素值由大到小逐层排序列，因此将剩下的元素调整成大顶堆只需从上往下逐层比较，找出最大元素并将其放在根结点的位置即构成了新的大顶堆。

调整的算法描述：输出堆顶元素可以将堆顶元素放在堆的最后，即将第1个元素与最后一个元素交换位置a[1] a[n]，则需要调整的元素序列就是a[1...n-1]。从根结点开始，如果其左右子树结点元素值大于根结点元素值，选择较大的一个进行交换，也就是如果a[2]>a[3]，则将a[1]与a[2]进行比较，如果a[1]>a[2]，则将a[1]与a[2]交换，否则不交换。如果a[2]<a[3]，则将a[1]与a[3]比较，如果a[1]>a[3]，则将a[1]与a[3]交换，否则不交换。逐层重复执行此操作，直到叶子结点，就完成了堆的调整，构成了一个新堆。

例如，以个大顶堆的元素序列为85，73，68，51，29，55，36，32，输出85后大顶堆的调整过程如图所示。

新的大顶堆同样满足条件a[i]≥a[2*i]且a[i]≥[2*i+1]。继续将堆顶元素73输出，即与最后一个元素36交换，重新按照上述过程调整堆，直到堆中没有元素需要调整，这就完成了一个队排序的过程，此时依次输出堆顶元素构成的序列就是一个有序的序列。

code:

#include<stdio.h>
void DispArray(int a[], int n);
void AdjustHeap(int a[], int s, int m);
void CreateHeap(int a[], int n);
void HeapSort(int a[], int n);
void main()
{
	int a[] = { 67,48,23,81,38,19,52,40 };
	int n = sizeof(a) / sizeof(a[0]);
	printf("排序前:");
	DispArray(a, n);
	HeapSort(a, n);
	printf("堆排序结果:");
	DispArray(a, n);
	getchar();
}
void DispArray(int a[], int n)
/*输出数组中的元素*/
{
	int i;
	for (i = 0; i<n; i++)
		printf("%4d", a[i]);
	printf("\n");
}
void CreateHeap(int a[], int n)
/*建立大顶堆*/
{
	int i;
	for (i = n / 2 - 1; i >= 0; i--)	/*从序号n/2-1开始建立大顶堆*/
		AdjustHeap(a, i, n - 1);
}
void AdjustHeap(int a[], int s, int m)
/*调整a[s...m]，使其成为一个大顶堆*/
{
	int t, j;
	t = a[s];								/*将根结点暂时保存在t中*/
	for (j = 2 * s + 1; j <= m; j *= 2 + 1)
	{
		if (j<m&&a[j]<a[j + 1])			/*沿关键字较大的孩子结点向下筛选*/
			j++;						/*j为关键字较大的结点的下标*/
		if (t>a[j])						/*如果孩子结点的值小于根结点的值，则不进行交换*/
			break;
		a[s] = a[j];
		s = j;
	}
	a[s] = t;								/*将根结点插入到正确位置*/
}
void HeapSort(int a[], int n)
/*利用堆排序算法对数组a中的元素进行排序*/
{
	int t, i;
	CreateHeap(a, n);		/*创建堆*/
	for (i = n - 1; i>0; i--)		/*将堆顶元素与最后一个元素交换，重新调整堆*/
	{
		t = a[0];
		a[0] = a[i];
		a[i] = t;
		printf("第%d趟排序结果:", n - i);
		DispArray(a, n);
		AdjustHeap(a, 0, i - 1);		/*将a[0..i-1]调整为大顶堆*/
	}
}

结果：

 【主要用途】

堆排序算法实现比较复杂，它主要适用于大规模的数据排序，例如，如果需要在100k个元素中找出前10个最小的元素或者最大元素则使用堆排序算法效率最高。

【稳定性和负杂度】

堆排序属于不稳定的排序算法。

堆排序的时间消耗主要是在建立堆和调整堆时，一个深度为h，元素个数为n的堆，其调整的比较次数最多为2(h-1)次，而建立堆比较次数最多为4n，一个完整的堆排序过程总共的比较次数为2（++...+）<2nlog2n，因此堆排序的平均时间复杂度和最坏的时间复杂度都是O(nlog2n)。

堆排序的空间复杂度O(1)。