7

Size: px

Start display at page:

Download "7"

参易
5 years ago
Views:

1 孙猛年 10 月 19 日 1

2 堆与优先队列列哈夫曼树 2

3 介绍一种特殊的完全二叉树这种二叉树的顺序存储表示堆优先队列列的概念及使用堆的实现方法 3

4 每个结点的值都小于 ( 或者都大于 ) 它的左右子树的根结点的值这种二叉树的广度优先周游序列列顺序表示中, 用于存放结点的顺序表具有如下性质 : k k i i k k 2i+ 1 2i

5 n 个元素的序列列仅当满足条件 : K =(k 0,k 1,,k n 1 ) 称为堆, 当且 k (1) k i 或 i k k 2i+ 1 2i+ 2 k (2) k i i k k 2i+ 1 2i+ 2 (i =0, 1,, bn/2c 1) 这一条件简称为堆序性 5

6 满足条件 (1) 的堆, 在对应的完全二叉树中等价于 : 每个子二叉树的根均大于等于其左右子结点 ; 因此在这个堆中, 根结点是最大结点故则称为大根堆满足条件 (2) 的堆, 在完全二叉树中等价于 : 每个子二叉树的根均小于等于其左右子结点因此在这个堆中, 根结点是最小结点故称为小根堆本节课主要讨论小根堆! 6

7 优先队列列是一种常见的抽象数据类型, 它遵循最小元素先出的原则优先队列列的基本操作有三个 : 向优先队列列里里插入一个元素 ; 在优先队列列中找出最小元素 ; 删除优先队列列中最小元素 7

8 ADT PriorityQueue is Operations PriorityQueue createemptypriqueue(void) 创建一个空优先队列列 int isempty(priorityqueue S) 若 S 为空, 则返回 1, 否则返回 0 void add(priorityqueue S, DataType e) 向 S 中添加元素 e DataType min(priorityqueue S) 返回 S 中的最小元素 void removemin(priorityqueue S) 删除 S 中的最小元素 end ADT PriorityQueue 8

9 优先关系代表了了数据的某种性质, 如用于描述各项工作的计划开始时间 ( 实际中, 模拟中都可能使用 ) 一个大项目中各种工作任务的急迫程度 ( 或截止期 ) 银行行客户的诚信评估, 用于决定优先贷款, 等等优先队列列的操作也很简单, 应包括创建, 判断空 ( 还可以有清空内容确定当前元素个数等 ) 插入元素, 访问和删除优先队列列里里 ( 当时最优先 ) 的元素 9

10 最常用来表示优先队列列的方法是 ( 小根 ) 堆由于堆与完全二叉树的内在联系, 下面表示优先队列列的定义与二叉树的顺序表示基本一样 : struct PriorityQueue { int MAXNUM; /* 元素个数的上限 */ int n; /* 实际元素个数 */ DataType *pq; /* 存放元素的数组的指针 */ }; /* 优先队列列类型 */ typedef struct PriorityQueue * PPriorityQueue; /* 指向优先队列列的指针类型 */ 10

11 插入要把一个新元素加入优先队列列根据堆的表示特点, 显然必须有某个元素要放到紧接着原有数组元素后面的位置, 并且还需要保持堆序性一个实现方法是 : 假设把新元素先放在已有元素后, 然后通过反复比较, 必要时交换该结点与对应的父结点, 直到堆序性重新被满足为止 11

13 每个结点的值都小于 ( 或者都大于 ) 它的左右子树的根结点的值这种二叉树的广度优先周游序列列顺序表示中, 用于存放结点的顺序表具有如下性质 : k k i i k k 2i+ 1 2i

15 void add_heap(ppriorityqueue papq, DataType x) { int i; if (papq->n >= papq->maxnum){ printf("full!\n"); return; } for (i = paqu->n; i > 0 && papq->pq[(i - 1) / 2] > x; i = (i - 1) / 2) papq->pq[i] = papq->pq[(i - 1) / 2]; /* 空位向根移动找插入位置 */ } papq->pq[i] = x; /* 将 x 插入 */ papq->n++; 15

17 在被删后, 根结点形成一个空位, 这时先考虑能否把处在堆中最后位置的结点填入这里里由于这样做可能破坏堆序性, 所以选择这个元素与根的两个子结点三者中最小的结点填入, 选择的结果可能使得原来的空位向叶结点方向传递如此反复交换, 最终到堆中最后结点小于等于空位的两个子结点时, 将最后结点填入这个空位 17

18 void removemin_heap(ppriorityqueue papq) { int s, i, child; DataType temp ; if (isempty_heap(papq)) {printf("empty!\n"); return;} s = --papq->n; /* 先删除 */ temp = papq->pq[s]; /* 把最后元素移到 temp*/ i =0; child = 1; while (child < s) { /* 找最后元素存放的位置 */ if (child < s - 1 && papq->pq[child] > papq->pq[child + 1]) child++; /* 选择较的结点 */ if (temp > papq->pq[child]) /* 空位向叶结点移动 */ { papq->pq[i] = papq->pq[child]; i = child; child = 2 * i + 1; } else break; /* 已经找到适当位置 */ } papq->pq[i] = temp; /* 把最后元素填 */ } 18

19 在删除操作过程中, 由于对每层最多只需要做 2 次比较, 而且循环是从树根到树叶进行行的, 所以这个删除程序的复杂性也是 O(log n) 判断优先队列列是否为空和取优先队列列中的最小元素都非常容易易实现时间代价均为 O(1) 19

20 离散事件的模拟利利用优先队列列设计一个对机场的模拟系统该机场有两条跑道, 飞机从空中飞来申请着陆, 同时地上的飞机申请起飞经常出现在操作系统的各种调度算法中! ( 堆 ) 排序 20

21 一种特殊的扩充二叉树带权的外部路路径长度哈夫曼树哈夫曼算法哈夫曼编码 21

22 if a<60 b= 不不及格 a<60 else: if a<70 不不及格 a<70 b= 及格及格 a<80 else: if a<80 b= 中等 else: if a<90 b= 良好 else: b= 优秀中等良好 a<90 优秀 22

23 分数所占比例例 5% 15% 40% 30% 10% a<80 a<70 a<90 a<60 中等良好优秀不不及格及格 23

24 在扩充二叉树中, 若 l i 为从根到第 i 个外部结点的路路径长度,m 为外部结点的个数则外部路路径长度 E= m i=1l i 如果每个外部结点都带有权值, 且第 i 个外部结点的权值为 w i, 则 WPL= m w i=1 i l i, 称做扩充二叉树的带权的外部路路径长度 24

25 给定一组 ( 无序 ) 实数 {w 1, w 2,.., w m }, 扩充二叉树 T 称为哈夫曼树或最优二叉树, 如果 T 满足 : (1) 有 m 个外部结点, 且分别以 w i 为 (i=1,,m) 其权值 ; (2)T 是满足条件 (1) 的扩充二叉树中带权的路路径长度 WPL 最小的 WPL= = 34 WPL=40 25

26 w={11,4,3,2}

27 (1) 由给定的 m 个权值 w={w 1, w 2,.., w m }, 构造包含 m 棵二叉树的集合 F = {T 1,T 2,,T m }, 其中二叉树 T i 只含权为 w i 的根结点 ; (2) 从 F 中选取两棵根结点权最小和次最小的树作为左右子树, 构造一棵新二叉树, 其根结点的权值为两棵子树的根结点权值之和 ; (3) 从 F 删除所选的两棵树, 把新构造的二叉树加入F; (4) 重复 (2) 和 (3), 直到 F 中只含一棵树为止 27

28 在这里里我们介绍一种存储表示, 该存储结构是在二叉树的 llink 和 rlink 基础上增加一个父结点的指针, 并且所有结点顺序存放在一个顺序表中在顺序表中, 每个结点的结构由四部分组成 : ww parent llink rlink 28

29 struct HtNode { /* 哈夫曼树结点的结构 */ int ww; int parent,llink,rlink; }; struct HtTree{ /* 哈夫曼树结构 */ int m; /* 外部结点的个数 */ int root; /* 哈夫曼树根在数组中的下标 */ struct HtNode *ht; /* 存放 2*m-1 个结点的数组 */ }; typedef struct HtTree *PHtTree; /* 哈夫曼树类型的指针类型 */ 29

30 PHtTree huffman(int m, int *w) { PHtTree pht; int i,j,x1,x2,m1,m2; pht = (PHtTree)malloc(sizeof (struct HtTree)); /* 分配空间 */ if (pht==null) { printf( Out of space!! \n ); return pht;} pht->ht=( struct HtNode) malloc(sizeof (struct HtNode)*(2*m-1)); if (pht==null) { printf( Out of space!! \n ); return pht;} for( i=0; i<2*m - 1; i++ ) {/* 置 ht 数组初态 */ pht->ht[i].llink = -1; pht->ht[i].rlink = -1; pht->ht[i].parent = -1; if (i<m) pht->ht[i].ww = w[i]; else pht->ht[i].ww = -1; } for( i=0; i < m - 1; i++ ) {/* 每循环一次构造一个内部结点 */ m1 = MAXINT; m2 = MAXINT; /* 相关变量量赋初值 */ x1 = -1; x2 = -1; for(j=0;j<m+i;j++) /* 找两个最小权的无父结点的结点 (m1<m2)*/ if (pht->ht[j].ww<m1 && pht->ht[j].parent==-1) { m2 = m1;x2 = x1; m1 = pht->ht[j].ww; x1 = j;} else if (pht->ht[j].ww<m2 && pht->ht[j].parent==-1) {m2 = pht->ht[j].ww; x2 = j;} pht->ht[x1].parent = m + i; pht->ht[x2].parent = m + i; pht->ht[m+i].ww = m1 + m2; pht->ht[m+i].llink = x1; pht->ht[m+i].rlink = x2; /* 构造内部结点 */ } pht->root = 2*m - 2; return pht; } 30 本算法具有平方复杂性能加快其速度吗?

31 对于一组权值 w = {2,3,5,7,11,13,17,19,23, 29,31,37,41}, 按照上述算法构造出的哈夫曼树如下图所示 : 31

32 设 d={d 1, d 2,.., d n } 为需要编码的字符集合, w={w 1, w 2,.., w n } 为 d 中各字符出现的频率 d 中字符的二进制编码称为最优前缀码, 如果使得 : (1) 按照给出的编码传输文件时, 通讯编码平均总长最短 ; (2) 若 d i d j, 则 d i 的编码不不可能是 d j 的编码的开始部分 ( 前缀 ) 最优前缀码的构造 : 利利用哈夫曼树构造哈夫曼编码 32

33 通过构造哈夫曼树, 实现哈夫曼编码 : (1) 以字符 d 1, d 2,.., d n 为外部结点标注, 把 w 1, w 2,.., w n 分别作为这 n 个外部结点的权, 构造一棵哈夫曼树 (2) 在得到的哈夫曼树中, 将所有从一个结点引向其左子结点的边标上二进制数字 0; 引向其右子结点的边标二进制数字 1 (3) 以从根结点到一个叶结点的路路径上的二进制数字序列列, 作为这个叶结点的字符的编码, 就是这个叶结点所代表字符的最优前缀编码, 称为哈夫曼编码 33

34 d = { d 1,d 2,,d 13 } w = { 2,3,5,7,11,13,17,19,23,29,31, 37,41 } 利利用哈夫曼算法构造其哈夫曼树 34

35 d 1 : ,d 2 : ,d 3 :101110, d 4 :10110, d 5 :0100, d 6 :0101, d 7 :1010, d 8 :000, d 9 :001, d 10 :011, d 11 :100, d 12 :110, d 13 :111 35

36 只要从二叉树的根结点开始, 用需要解码的二进制位串串, 从头开始与二叉树根结点到子结点边上标的 0 1 相匹配, 确定一条到达树叶结点的路路径一旦到达树叶结点, 则译出一个字符然后再回到根结点, 从二进制位串串中的下一位开始继续解码 36

37 d={y,a,h,m,p,i} w={1,2,3,5,7,9} 27 哈夫曼编码 : 0 1 Y : 0110 A : 0111 H : 010 M : P : 1 0 I : 11 M P 7 I H Y 1 2 A 37

38 假设现在有 m 个已经排序的文件 {d 1,d 2,,d n }, 每个文件包含的记录个数对应为 {w 1,w 2,,w n }; 可以采用两两合并的方法, 把所有文件的记录合到一个大文件中, 使这个文件中的记录全部排序问 : 采用怎样的合并次序才能使得移动记录个数最少? 答案 : 按照哈夫曼树的结构从外部结点到根结点逐层进行行合并, 一定是一种最佳的 ( 但并非唯一的 ) 合并顺序 38

39 归纳法可证具体证明过程可见 : algoviz.org/opendsa/books/opendsa/html/huffproof.html 39

40 堆的概念, 与二叉树的联系优先队列列的概念, 表示, 实现和应用哈夫曼树的概念, 算法和应用二叉树的应用非常广泛, 这里里仅仅是两个简单的例例子由于它们使用广泛, 非常有名, 所以特别在这里里介绍值得注意的是 : 在这两个应用中实际仅仅使用了了二叉树的观点 ( 没有应用二叉树的 ADT) 后面还会看到许多的应用二叉树的例例子 40

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用