2019/3/11
数据结构
8
2019/3/11
数据结构
9
3. 筛选算法
void HeapAdjust(datetype R[ ], int s, int t) { /*以R[s]为根的子树只有R[s]与其左右孩子之间可能不满足 堆特性*/ /*进行调整使以R[s]为根的子树成为大顶堆*/ datetype rc; /*缓冲变量*/ rc=R[s]； i=s; for(j=2*i; j<=t; j=2*j) /*沿关键码较大的孩子结点向下筛选*/ { if(j<t && R[j].key<R[j+1].key) j=j+1; /* j指向R[i]的关键码较大的孩子*/ if(rc.key > R[j].key) break; /*不用调到叶子就到位了*/ R[i]=R[j]; i=j; /*准备继续向下调整 */ } R[i]=rc； /*插入*/ } 2019/3/11 数据结构
10
4、堆排序的实现
初步的堆排序算法： 1、建成初始堆； 2、for (i=n;i>1;i--) { R[1]<=>R[i]; HeapAdjust(R,1,i-1); }
2019/3/11
数据结构
11
再讨论第一个问题：对原始排序表建初始堆的过程。
对原始序列建堆过程，就是一个反复进行筛选的过程。 仍然通过对应的完全二叉树分析：对 n 个结点的完全二叉树， 可以认为：以叶子为根的子树（只有它自己）已满足堆特性，因 此从最后一个分支结点开始，把每棵子树调整为堆，直到根结点 为止，整棵树成为堆。 n 最后一个分支结点是第 个结点。 2
2019/3/11 数据结构 2
2．堆排序
堆特点：堆顶元素是整个序列中最大(或最小)的元素。 若将排序表按关键码建成堆，堆顶元素就是选择出的最大 元素（或最小），这样就得到n个元素中的第一个的元素。 然后，再对剩下的n-1个元素建成堆，得到n个元素中关键 码次大 (或次小)的元素。以此类推，如此反复，直到进行n1次后，排序结束，便得到一个按关键码有序的序列。称这个 过程为堆排序。
仅需调整一次，
堆建成 。
2019/3/11
数据结构
7
第二个问题的背景： 输出堆顶元素后，将堆底元素送入堆顶（或将堆顶元素 与堆底元素交换），堆可能被破坏。 破坏的情况仅是根结点和其左右孩子之间可能不满足堆的 特性，而其左右子树仍然是局部的堆。
在这种情况下，将其R1 … Ri整理成堆。 （i=n-1..1)
2019/3/11
数据结构
3
因此，实现堆排序需解决两个问题： 1. 如何将n个元素的排序序列按关键码建成堆（初始堆）； 2. 怎样将剩余的n-1个元素按其关键码调整为一个新堆。
2019/3/11
数据结构
4
2. 怎样将剩余的n-1个元素按其关键码调整为一个新堆。 假设有一个大根堆，当输出堆顶元素（根结点）后，以堆中 最后一个元素替代它。此时根结点的左子树和右子树均为堆， 则只需自上而下进行调整即可。 首先将堆顶元素与其左、右子树根结点的值进行比较，如果 堆顶元素比它的两个子结点都大，则已经是堆；否则，让堆顶 元素与其中较大的孩子结点交换，先让堆顶满足堆的性质。可 能因为交换，使交换后的结点为根的子树不再满足堆的性质， 则重复向下调整，当调整使新的更小子树依旧满足堆的性质时， 重新建堆的过程结束。这种自上而下的建堆过程称为结点向下 的“筛选”。图2是一个大根堆的排序输出过程。
2019/3/11
c. 右子树不满 d. 到了叶子结 足堆，继续调 点，调整结束， 整。 堆建成。
数据结构
6
85
30
53
53 47 85 91 30 36 16 85
47
24 91 36
53
16 30 91 24
47 36
16
24
堆调整结束。
R1 与 Rn-1 交 换 ， 堆被破坏。 对 R1 与 Rn-2 调 整。
91 47 24 16 85 36 53 30
小顶堆 ：16，36，24，85，47，30，53，91
16 36 85 91 24
47 30 53
如果该序列是一个堆，则对应的这棵完全二叉树的特点是： 所有分支结点的值均不小于 (或不大于)其子女的值，即每棵子 树根结点的值是最大(或最小)的。 堆特点：堆顶元素是整个序列中最大(或最小)的元素。
2019/3/11 数据结构 13
30 24 47 36 85 53 91 16 47 24
30 91 36 53
85
c. 以 R3 为根的子树满足 堆特性。 再将以 R2 结点为根的子树 调整为堆；
堆排序(Heap Sort)
堆排序(Heap Sort) 1堆的定义
设有n个元素的序列 R1，R2，…，Rn，当且仅当满足下述 关系之一时，称之为堆。
k2i ki ki≥ 其中i=1,2,…,n/2
前者称为小顶堆，后者称为大顶堆。
k2i+1
如：序列 12,36,24,85,47,30,53,91是一个小顶堆；
序列 91,47,85,24,36,53,30,16是一个大顶堆。
2019/3/11 数据结构 1
在完全二叉树上，双亲和左右孩子之间的编号就是i和2i、 2i+1的关系。因此一个序列可以和一棵完全二叉树对应起来， 用双亲其左、右孩子之间的关系可以直观的分析是否符合堆的 特性。
大顶堆：91，47，85，24，36，53，30，16
2019/3/11
数据结构
5
91 47 24 16 36 85 53 30 91 24 47
16
85 36 53 30 91 24 47
85 16 36 53 30 24 47
85 53 36 16 30
91
a.初始堆
b.堆被破坏
输出堆顶元素 , 调整：根结点 再将最后一个 与左右子女较 元素放入堆顶 ( 为 了 操 作 简 便 ， 大者比较，若 将 堆 顶 元 素 R1 比根小，交换。 与Rn交换)。
2019/3/11
数据结构
12
【例】建堆的过程： 设初始排序序列：30 24 85 16 36 53 91 47 ，建成大顶堆。
30 24 16 47 a.8个结点的初始状态。 从R4结点开始调整； 36 85 53 91 16
b.调整结束后，以R4为
根的子树满足堆特性。 再将以R3结点为根的 子树调整为堆；