第九章堆与优先队列

1、第九章第九章 堆与优先队列堆与优先队列山东财经大学山东财经大学管理科学与工程学院管理科学与工程学院9.1 优先队列的基本概念优先队列的基本概念定义定义优先队列中的每一个元素都有一个优先级值。优先队列中优先队列中的每一个元素都有一个优先级值。优先队列中元素元素x的优先级值记为的优先级值记为p(x)，它可以是一个实数，也可以，它可以是一个实数，也可以是一个一般的全序集中的元素。是一个一般的全序集中的元素。基本运算基本运算Size( )u返回优先队列中元素个数。返回优先队列中元素个数。Emputya()u判断优先队列是否为空判断优先队列是否为空Min( )u返回优先队列中具有最小优先级值的元素。返回

2、优先队列中具有最小优先级值的元素。push(x)u将元素将元素x插入优先队列。插入优先队列。Pop_Min(x)u删除优先队列中具有最小优先级值的元素，并保存到删除优先队列中具有最小优先级值的元素，并保存到x中中优先队列举例优先队列举例排队上车，老弱病残者优先上车排队上车，老弱病残者优先上车排队候诊，危急病人优先就诊排队候诊，危急病人优先就诊洗相馆为顾客洗照片，加钱加急者优先洗洗相馆为顾客洗照片，加钱加急者优先洗分时操作系统运行程序，小程序优先分时操作系统运行程序，小程序优先贪心算法对解分量的选择，按元素的某种特征值，大贪心算法对解分量的选择，按元素的某种特征值，大( (或小或小) )的优先的

3、优先在一个集合中搜索，按元素的某种特征值，大在一个集合中搜索，按元素的某种特征值，大( (或小或小) )的优先的优先处理或服务时只关心对象中谁的优先级最高通常处理或服务时只关心对象中谁的优先级最高通常的队列是一种优先队列最先到者优先级最高的队列是一种优先队列最先到者优先级最高9.3 优先级树和堆优先级树和堆 极小化优先级树极小化优先级树树中每一结点存储一个元素。树中每一结点存储一个元素。任一结点中存储的元素的优先级值不大于其儿子结点任一结点中存储的元素的优先级值不大于其儿子结点中存储的元素的优先级值中存储的元素的优先级值u父结点的优先级不高于其儿子结点的优先级。父结点的优先级不高于其儿子结点的

4、优先级。越接近根的结点中的元素的优先级越高越接近根的结点中的元素的优先级越高 极大化优先树极大化优先树堆堆如果一棵如果一棵优先级树是一棵优先级树是一棵近似满二叉树近似满二叉树，那么，这棵，那么，这棵具有优先级性质的近似满二叉树具有优先级性质的近似满二叉树( (外形像堆外形像堆) )就叫做堆就叫做堆 极小化堆极小化堆 极大化堆极大化堆 8 81616 9 9 1 1 6 6 2 2 11111010 5 5 4 4 1 1 6 6 8 81212 9 91616 2 2 1111 5 5 1 14 4n关键字：关键字：12 19 65 38 27 731219653827例如例如:是堆（最小堆）

5、是堆（最小堆）73n关键字：关键字：12 19 65 38 27 3612 19 65 38 27 36 121965382773是堆是堆36不不 12 19 27 11 20 12 19 65 38 27 73 12 12 19 27 19 65 11 20 38 27 73 堆的判断练习堆的判断练习非非 堆堆 是是 堆堆堆的删除堆的删除删除堆中最底层、最右边的叶结点，并用其中所删除堆中最底层、最右边的叶结点，并用其中所存放的元素取代树根中应该删除的元素，然后对存放的元素取代树根中应该删除的元素，然后对堆进行调整。堆进行调整。 30301010 1515 2020 25254040 2525

6、 5050 30305050 1515 2020 25254040 2525 30301515 5050 2020 25254040 2525 30301515 2020 5050 25254040 2525堆的插入堆的插入先将存放新元素的结点添加在堆的最底层，使之先将存放新元素的结点添加在堆的最底层，使之成为一棵近似满二叉树，然后进行调整。成为一棵近似满二叉树，然后进行调整。 30301515 2020 5050 25254040 2525 8 8 30301515 2020 5050 25258 8 2525 4040 30301515 2020 5050 8 82525 2525 404

7、0 30308 8 2020 5050 15152525 2525 4040建堆建堆 自下而上，从右到左自下而上，从右到左（26， 5，77，1，61， 11，59， 15， 48， 19）126775591161154819126775591161154819初始完全二叉树126775591161154819119611267755911191548612481建堆建堆 75, 87, 68, 92, 88, 61, 77, 96, 80, 72霍夫曼编码使用一个字符在文件中出现的频率表来建立使用一个字符在文件中出现的频率表来建立一个用一个用0，1串表示各字符的最优表示方法串表示各字符的最优

8、表示方法树的带权路径长度树的带权路径长度：树中所有叶子树中所有叶子结点的带权路径长度结点的带权路径长度之和之和27 9 75492WPL(T)= 72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 54前缀码前缀码定义定义为了解码时不会出现二义性，要求任意为了解码时不会出现二义性，要求任意一个字符的编码不能是另一个字符的前缀。一个字符的编码不能是另一个字符的前缀。例例a0，b101，c100，d111， e1101，f1100001011101aabe霍夫曼编码霍夫曼编码构造最优前缀码的算法构造最优前缀码的算法根据给定的根据给定的 n 个权值个权值 w1,

9、 w2, , wn构造构造 n 棵棵二叉树的集合二叉树的集合F = T1, T2, , Tn，其中每棵，其中每棵二叉树中均只含一个带权值二叉树中均只含一个带权值 为为 wi 的根结点的根结点,其左、其左、右子树为空树右子树为空树;在在 F 中选取其根结点的权值为最小的两棵二叉树，中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和结点的权值之和;从从F中删去这两棵树，同时加入刚生成的新树中删去这两棵树，同时加入刚生成的新树;重

10、复重复 (2) 和和 (3) 两步，直至两步，直至 F 中只含一棵树为止。中只含一棵树为止。例例 给定一组权值为给定一组权值为2，4，5，7，试构造一棵哈夫曼树。，试构造一棵哈夫曼树。（1）2475（2）2475426（3）42675（4）4267511（5）4267511184275哈夫曼树不唯一具有n个叶结点的哈夫曼树必有2n-1个结点霍夫曼树性质霍夫曼树性质 霍夫曼树不唯一霍夫曼树不唯一 霍夫曼树中没有度为霍夫曼树中没有度为1的结点的结点 叶子结点个数为叶子结点个数为n的霍夫曼树的总的结点个数是的霍夫曼树的总的结点个数是:2n-1例例已知某系统在通信联络中只可能出现八种字符，已知某系统在通信联络中只可能出现八种字符，其概率分别为其概