堆排序严蔚敏 数据结构之选择排序之堆排序(参考严蔚敏数据结构)

/*在线_ITWAP_内容页_正文上方图片广告 创建于 2017-01-11*/ var cpro_id = "u2873737"; -->

//堆是一种存储结构,是满足完全二叉树的顺序存储结构//理解大顶堆//堆调整函数是对以当前结点为根结点的堆进行调整使其成为大顶堆,且默认只有根结点可能不满足大顶堆,根结点的所有子孙结点(如果有)皆满足大顶堆//创建大顶堆函数是对所有的结点构成的堆经过从i=[n/2]直至i=1反复调用堆调整函数实现的//堆排序函数是创建大顶堆之后,重复进行如下操作最终完成堆排序:将堆顶元素和最末尾的元素互换,更新后的末尾元素到位(最终排序成功后的位置)并不在堆调整范围内, //调用堆调整函数(因为只有堆顶元素可能不满足最大堆性质) #include<iostream> using namespace std; #define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度 #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b)) typedef int InfoType; // 定义其它数据项的类型 typedef int KeyType; // 定义关键字类型为整型 typedef struct RedType // 记录类型 { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项,具体类型在主程中定义 }RedType; typedef struct SqList // 顺序表类型 { RedType r[MAXSIZE 1]; // r[0]闲置或用作哨兵单元 int length; // 顺序表长度 }SqList; typedef SqList HeapType; // 堆采用顺序表存储表示 void HeapAdjust(HeapType &H, int s, int m)//局部调整 { // 已知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&<(H.

r[j].key, H.r[j 1].key))//如果j下标对应key有右兄弟且key小于右兄弟key j; // 更新j,j为key较大的记录的下标 if (!LT(rc.key, H.r[j].

key)) break; // rc应插入在位置s上 else { H.r[s] = H.r[j]; s = j; } } H.r[s] = rc; // 插入 } void CreateMTHeap(HeapType &H)//全局调整 {// 把H.

r[1..H.length]建成大顶堆 int i; for (i = H.length / 2; i > 0; --i) HeapAdjust(H, i, H.

length);//调用堆调整函数使i下标对应的结点为根结点的堆成大顶堆 } void HeapSort(HeapType &H) { // 对顺序表H进行堆排序 RedType t; int i; CreateMTHeap(H); for (i = H.

length; i>1; --i) { /*将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换,之后i下标对应元素到位(排序后应该在的位置)*/ t = H.

r[1]; H.r[1] = H.r; H.r = t; /*****************************************************************************************************8*/ 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.key, H.r.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; h.length = N; printf("排序前:n"); print(h); HeapSort(h); printf("排序后:n"); print(h); }