（13，38，27，50，76，65，49，97） 13，38，27，50，76，65，49，97）
97 27 49 13 输出：13 50 38 76 65 27 49 13 输出：13 50 38 76 65 27 49 97
97 38 50 13 输出：13 27 76 65 49 27 13 97 50 76
38 49 65 27 13 输出：13 27 97 50 76
65 49 38 27
输出：13 27 38
8
49 50 97 13 输出：13 27 38 76 38 65 27 13 97 50 49
76 65 38 27 13 输出：13 27 38 49 97 76 49
50 65 38 27
14
97 65 38 27
输出：13 27 38 49 50 65 76
10
算法 :堆调节 void HeapAdjust (HeapType &H, int s, int m) { // 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数依据 已知H.r[s..m]中记录的关键字除 中记录的关键字除H.r[s].key之外均满足堆的定义 之外均满足堆的定义，
{12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 是小顶堆 {12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆 14,
1
若将该数列视作完全二叉树，则 r2i 是 ri 的左孩子； 的左孩子； 若将该数列视作完全二叉树， 的右孩子。 r2i+1 是 ri 的右孩子。
4
typedef SqTable heapType
void HeapSort ( HeapType &H ) CreateHeap(H); //建立初始堆 ｛ CreateHeap(H); //建立初始堆 H.r[1] H.r[n]; //堆顶元素与最后一个元素交换 //堆顶元素与最后一个元素交换 for(i=nfor(i=n-1; i>1; i--) //连续进行堆调节和交换 i--) //连续进行堆调节和交换 { HeapAdjust(H); HeapAdjust(H); H.r[1] H.r[i]; } } 堆排序需解决的两个问题： 堆排序需解决的两个问题：
//建堆 //建堆
左/右子树都已经调整为堆 void CreateHeap(HeapType &H) { for (i=H.length/2;i>0;i--) (i=H.length/2;i>0;i--) 最后只要调整根结点，使整个二叉树是个“堆” HeapAdjust(H, i, H.length); 即可。
11
建堆是一个从下往上进行“筛选”的过程。 建堆是一个从下往上进行“筛选”的过程。 例如: 原始序列为（40,55,49,73,12,27,78,81,64,36） 例如 原始
从第一个非叶节点开始调节
98 40 98 49 36 12 27 40 49 98
81 55 81 73 55 73 81 64 12 36
6
大顶堆调节过程： 大顶堆调节过程：
大顶堆的排序结果是升序排序
12 73 81 64 73 55 12 64 98 12 36
81 12 98
比较
49 27 40
是大顶堆
输出98（ 98 和 12 进行互换）之后，它就不是堆了 不 需要对它进行“筛选”
7
例：小顶堆 13 38 50 97 76 65
13 27 38 27 76 65 49
83
38
11
9 97
50
堆序列是完全二叉树，则堆顶元素 堆序列是完全二叉树， 完全二叉树的根）必为序列中n （完全二叉树的根）必为序列中n 个元素的最小值或最大值
3
堆排序
堆排序即是利用堆的特性对记录序列进行排序的 一种排序方法
堆排序的过程
对n个数据的原始无序序列建堆，输出堆顶元素 个数据的原始无序序列建堆， 将剩下的n 个元素调整为堆， 将剩下的n-1个元素调整为堆，输出堆顶元素 将剩下的n 个元素调整为堆， 将剩下的n-2个元素调整为堆，输出堆顶元素 …….. …….. 剩下的最后一个元素， 剩下的最后一个元素，本身就是堆
13
堆排序的时间复杂度分析： 堆排序的时间复杂度分析：
1. 对深度为 k 的堆，“筛选”所需进行的关键字 的堆， 筛选” 比较的次数至多为2(k 1)； 2(k比较的次数至多为2(k-1)； 2. 对 n 个关键字，建成深度为h(=log2n+1)的堆， 个关键字， (= +1)的堆 的堆， 所需进行的关键字比较的次数至多 4n； 3. 调整“堆顶”n-1次，总共进行的关键字比较的次 调整“堆顶” 数不超过 2 (log2(n-1)+log2(n-2)+…+log22)<2n(log2n) ( (n(n因此，堆排序的时间复杂度为O(nlogn)。 因此，堆排序的时间复杂度为O(
// 关键字的大小对H.r[s]进行调整，使H.r[s..m]成为一个大顶堆(对其中记录的关 关键字的大小对H.r[s]进行调整 进行调整， H.r[s..m]成为一个大顶堆 成为一个大顶堆( 键字而言) 键字而言)
rc = H.r[s]; // 暂存根结点的记录 for ( j=2*s; j<=m; j*=2 ) { // 沿key较大的孩子结点向下筛选 key较大的孩子结点向下筛选 if ( j<m && H.r[j].key<H.r[j+1].key ) ++j; // j为key较大孩子记录的下标 j为key较大孩子记录的下标 if ( rc.key >= H.r[j].key ) break; // 不需要调整 H.r[s] = H.r[j]; s = j; // 把大关键字记录往上调 } H.r[s] = rc; // 回移筛选下来的记录 } // HeapAdjust
堆的定义
完全二叉树的性质？ 完全二叉树的性质？
堆是满足下列性质的数据序列{ 堆是满足下列性质的数据序列{r1, r2, …，rn}：
r i ≤r r i ≥r 2 i 2 i (小顶堆 或 小顶堆) (大顶堆 大顶堆) 小顶堆 大顶堆 2 i r i+1 ≤ r i r2i+1 ≥ r
输出：13 27 38 49
97 76 50 13 输出：13 27 38 49 50 49 38 65 27 13 50 76 49
65 97 38 27 13 输出：13 27 38 49 50 50 76 49
97 65 38 27
输出：13 27 38 49 50 65
9
76 97 50 13 输出：13 27 38 49 50 65 97 76 50 13 输出：13 27 38 49 50 65 76 97 49 38 65 27 49 38 65 27 13 50 76 49
ri r2i
例如: 例如
12 36 65 81 73 55 40 49 14 34 27 98
2
r2i+1
{12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49}
不 是堆
例 （96，83，27，38，11，9） 96，83，27，38，11，
96
例 （13，38，27，50，76，49，97） 13，38，27，50，76，65，49，97）
如何由一个无序序列建成一个堆？ 如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素， 如何在输出堆顶元素之后，调整剩余元素，使 之成为一个新的堆？ 之成为一个新的堆？ 筛选
5
第二个问题解决方法——筛选 第二个问题解决方法——筛选
所谓“筛选”指的是，对一棵左/ 所谓“筛选”指的是，对一棵左/右子树均为堆的 完全二叉树， 调整” 完全二叉树，“调整”根结点使整个二叉树也成为 一个堆 方法：输出堆顶元素之后，以堆中最后一个元素替 方法：输出堆顶元素之后， 代之；然后将根结点值与左、 代之；然后将根结点值与左、右子树的根结点值进 行比较，并与其中小者进行交换；重复上述操作， 行比较，并与其中小者进行交换；重复上述操作， 直至叶子结点，将得到新的堆， 直至叶子结点，将得到新的堆，称这个从堆顶至叶 子的调整过程为“筛选” 子的调整过程为“筛选”
}
12
算法 :堆排序 void HeapSort ( HeapType &H ) { // 对顺序表H进行堆排序。 对顺序表H进行堆排序。 for ( i=H.length/2; i>0; --i ) --i // 把H.r[1..H.length]建成大顶堆 H.r[1..H.length]建成大顶堆 HeapAdjust ( H, i, H.length ); w=H.r[1] ; H.r[1]= H.r[H.length]; H.r[H.length]=w; //交换"堆顶"和"堆底"的记录 //交换 堆顶" 交换" 堆底" for ( i=H.length-1; i>1; --i ) { i=H.length--i HeapAdjust(H, 1, i); // 从根开始调整，将H 重新调整为大顶堆 从根开始调整， w=H.r[1]; H.r[1]=H.r[i]; H.r[i]=w; // 相互交换 } }