堆排序（第十章 P280 算法10.10,10.11）_下列函数为堆排序中的堆调整过程(调整h.r[s]的关键字,使h.r[s..m]成为一小顶堆)。

 

目录

 

 

堆排序

概述：

排序过程：

              建初始堆的过程

              输出堆顶元素并调整建新堆的过程

算法性能：

堆排序与快速排序的比较：

---

 

 

堆排序

 

概述：

 

堆排序是利用堆的性质进行的一种选择排序。

堆实际上是一棵完全二叉树，其满足性质：任何一结点大于等于或者小于等于其左右子树结点。

堆分为大顶堆和小顶堆，满足 “任何一结点大于等于其左右子树结点” 的称为大顶堆，满足 “任何一结点小于等于其左右子树结点” 的称为小顶堆。

由上述性质可知：大顶堆的堆顶肯定是最大的，小顶堆的堆顶是最小的。

 

 

排序过程：

 

确定最后一个非叶子结点：

其实这是有一个公式的，设二叉树结点总数为 n，则最后一个非叶子结点是第 ⌊n/2⌋ 个。

数组当中确定当前结点的左右孩子位置：

设当前结点下标是 i，则其左孩子的下标是 2i，右孩子的下标是 2i+1。请注意：这是建立在数组下标从 1 开始的情况。若数组下标从 0 开始，则其左右孩子下标还各需多加一个 1。

 

 

建初始堆的过程：

 

此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 ⌊n/2⌋=8/2=4，也就是下面的97结点），从左至右，从下至上进行调整。

找到第二个非叶节点65，由于[13,65,27]中13元素最小，13和65交换。

找到下一个非叶节点38，由于[38,49,76]中38元素最小，不需要交换。

找到下一个非叶节点49，由于[38,49,13]中13元素最小，13和49交换。

这时，交换导致了子根[65,49,27]结构混乱，继续调整，[65,49,27]中27最小，交换27和49。

此时，我们就将一个无序序列构造成了一个小顶堆。

 

 

输出堆顶元素并调整建新堆的过程：

 

将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

 

将堆顶元素13和末尾元素97进行交换

当我们删除一个最小堆的堆顶（并不是完全删除，而是替换到最后面），经过自我调节，第二小的元素就会被交换上来，成为最小堆的新堆顶。

重新调整结构，使其继续满足堆定义

再将堆顶元素27与末尾元素97进行交换，得到第二小元素。

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序。此处略。

 

 

算法性能：

 

空间复杂度：由于没有开辟额外的空间，堆排序仅需一个记录大小供交换用的辅助空间，所以空间复杂度为1 。

时间复杂度：

二叉堆的节点下沉调整（HeapAdjust 方法）是堆排序算法的基础，这个调节操作本身的时间复杂度：假设二叉堆总共有n个元素，那么下沉调整的最坏时间复杂度就等同于二叉堆的高度，也就是O（logn）。

我们再来回顾一下堆排序算法的步骤：

• 1. 把无序数组构建成二叉堆。
• 2. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。

第一步，把无序数组构建成二叉堆，需要进行n/2次循环。每次循环调用一次 HeapAdjust 方法，所以第一步的计算规模是  n/2 * logn，时间复杂度O（nlogn）。

第二步，需要进行n-1次循环。每次循环调用一次 HeapAdjust 方法，所以第二步的计算规模是 （n-1） * logn ，时间复杂度 O（nlogn）。

两个步骤是并列关系，所以整体的时间复杂度同样是 O（nlogn）。

 

 

堆排序与快速排序的比较：

 

相同点：

堆排序和快速排序的平均时间复杂度都是 ， 并且都是不稳定排序。

不同点：

1. 快速排序的最坏时间复杂度是  ，而堆排序最坏时间复杂度稳定在  。
2. 快速排序的递归和非递归方法空间复杂度都是 O（n），而堆排序的空间复杂度是 O（1）。

 

 

 

 

代码：

 

#include<stdio.h> /* EOF(=^Z或F6),NULL */
 
 /*  对两个数值型关键字的比较约定为如下的宏定义 */
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
 
 
typedef int InfoType; /* 定义其它数据项的类型 */
 
/* ---------------------------    待排记录的数据类型     ------------------------------*/
 
#define MAXSIZE 20 /* 一个用作示例的小顺序表的最大长度 */
typedef int KeyType; /* 定义关键字类型为整型 */
typedef struct
{
	KeyType key; /* 关键字项 */
	InfoType otherinfo; /* 其它数据项，具体类型在主程中定义 */
}RedType; /* 记录类型 */
 
typedef struct
{
	RedType r[MAXSIZE + 1]; /* r[0]闲置或用作哨兵单元 */
	int length; /* 顺序表长度 */
}SqList; /* 顺序表类型 */
 
 
/* ------------------------------------------------------------------------------------------*/
typedef SqList HeapType; /* 堆采用顺序表存储表示 */
 
 
 
void HeapAdjust(HeapType *H, int s, int m) /* 算法10.10 */
{ /* 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数 */
  /* 调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言) */
	RedType rc;
	int j;
	rc = (*H).r[s];
	for (j = 2 * s; j <= m; j *= 2)
	{ /* 沿key较大的孩子结点向下筛选 */
		if (j < m&&LT((*H).r[j].key, (*H).r[j + 1].key))
			++j; /* j为key较大的记录的下标 */
		if (!LT(rc.key, (*H).r[j].key))
			break; /* rc应插入在位置s上 */
		(*H).r[s] = (*H).r[j];
		s = j;
	}
	(*H).r[s] = rc; /* 插入 */
}
 
void HeapSort(HeapType *H)
{ /* 对顺序表H进行堆排序。算法10.11 */
	RedType t;
	int i;
	for (i = (*H).length / 2; i > 0; --i) /* 把H.r[1..H.length]建成大顶堆 */
		HeapAdjust(H, i, (*H).length);
	for (i = (*H).length; i > 1; --i)
	{ /* 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换 */
		t = (*H).r[1];
		(*H).r[1] = (*H).r[i];
		(*H).r[i] = t;
		HeapAdjust(H, 1, i - 1); /* 将H.r[1..i-1]重新调整为大顶堆 */
	}
}
 
void print(HeapType H)
{
	int i;
	for (i = 1; i <= H.length; i++)
		printf("(%d,%d)", H.r[i].key, H.r[i].otherinfo);
	printf("\n");
}
 
#define N 8
void main()
{
	RedType d[N] = { {49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8} };
	HeapType h;
	int i;
	for (i = 0; i < N; i++)
		h.r[i + 1] = d[i];
	h.length = N;
	printf("排序前:\n");
	print(h);
	HeapSort(&h);
	printf("排序后:\n");
	print(h);
}

运行结果：