009优先队列3.ppt

* * 霍夫曼编码 主要用途是实现数据压缩。 设给出一段报文： CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 }。 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36. 若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。 因各字符出现的概率为{ 2/18, 7/18, 4/18, 5/18 }，化整为 { 2, 7, 4, 5 }。 * * 以它们为各叶结点上的权值，建立霍夫曼树，左分支赋 0，右分支赋 1。 霍夫曼编码(变长编码)： A : 0 T : 10 C : 110 S : 111 总编码长度：7*1+5*2+( 2+4 )*3 = 35。 总编码长度正好等于 霍夫曼树的带权路径长 度WPL。 比等长编码的情形要短。 霍夫曼编码树 * * 优化程序-编制分数转化程序 if (a60) b=‘不及格’ else if (a70) b=‘及格’ else if (a80) b=‘中等’ else if (a90) b=‘良好’ else b=‘优秀’ * * 数据实例 分数 0-59 60-69 70-79 80-89 90-100 比例数 0.05 0.15 0.40 0.30 0.10 * * A60 A70 A80 A90 不及格 及格 中等 优秀 良好 N N N N Y Y Y Y * * 70≤A80 80≤A90 60≤A70 A60 中等 良好 及格 优秀 不及格 N N N N Y Y Y Y * * A80 A90 中等 良好 及格 优秀 不及格 N N N N Y Y Y A70 A60 Y 10000个输入，各需要多少次比较 * * 归并排序 练习23 * 练习题 1. 一组序列的关键码为： {28、19、27、49、56、12、10、25} 该序列是否是堆？若不是，写出建立的初始堆（最大堆）。 利用堆排序的方法对该序列进行非递减排列，给出堆排序的主要过程。 给出在初始堆中插入一新元素60后的堆结构。 2.在一段文字中，7个常用汉字及出现频度如下： 的 地 于 个 和 是 有 20 19 18 17 15 10 1 要求： ⑴ 画出对应的Huffman树； ⑵ 求出每个汉字的Huffman编码。 第9章优先队列(Priority Trees) * 本章内容 9.1 引言 9.2 线性表 9.3 堆 9.4 左高树 9.5 应用 * * 堆的实现 堆排序 左高树 霍夫曼编码 本章重点 * 9.5 应用 9.5.1 堆排序(Heap Sort) 9.5.2 机器调度(Machine Scheduling) 9.5.3 霍夫曼编码(Huffman Codes) * 9.5.1 堆排序(Heap Sort) 可利用堆来实现n个元素的排序，每个元素的关键值为优先权。 堆排序算法： 将要排序的n个元素初始化为一个最大(小)堆. 每次从堆中提取（即删除）元素。 如果使用最大堆,各元素将按非递减次序排列。 如果使用最小堆,各元素将按非递增次序排列。 时间复杂度： 初始化所需要的时间为(n)，每次删除所需要的时间为O(logn) ，因此总时间为O(nlogn) 。 * 例：堆排序 A=[20,12,35,15,10,80,30,17,2,1] 2 80 30 17 35 1 20 10 12 15 * 例：堆排序 初始化最大堆 2 20 30 12 35 1 80 10 17 15 * 例：堆排序 80 80 35 80 35 30 80 35 30 20 * * template class T void HeapSort(T a[], int n) {// 利用堆排序算法对a[1:n] 进行排序 // 创建一个最大堆 MaxHeapT H(1); H.Initialize(a,n,n) ; // 从最大堆中逐个抽取元素 T x; for (int i = n-1; i = 1; i--) { H.DeleteMax(x) ; a[i+1] = x; } // 在堆的析构函数中保留数组a H.Deactivate(x) ; } 堆排序算法实现 * 9.5.3 霍夫曼编码(Huffman Codes)