最小最大堆课件.ppt

《最小最大堆课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、高级数据结构——最小最大堆Min-MaxHeap双端优先队列与最小最大堆双端优先队列是一种支持下列操作的数据结构：（1）插入一个具有任意key值的元素（2）删除key值最大的元素（3）删除key值最小的元素当只需要支持两个删除操作之一时采用最小堆或最大堆支持以上全部操作最小最大堆定义：最小最大堆是一棵完全二叉树，且其中每个元素有一个key数据成员。树的各层交替为最小层和最大层。根结点在最小层。设x是最小最大堆的任意结点。若x在最小（最大）层上，则x中的元素的key值在以x为根的子树的所有元素中是最小（最大）的。位于最小（最大）层的结点称为最小（最大）结点。Min-MaxHeap依序插入

2、10和801.2.3.4.5.新節點80位於maxlevel且大於其父節點12，故不交換。6.templatevoidMinMaxHeap::Insert(constElement&x){if(n==MaxSize){MinMaxFull();return;}n++;intp=n/2;//p是新结点的双亲if(!p){h[1]=x;return;}//插入初始时为空的堆switch(level(p)){caseMIN:if(x.key

3、Max(n,x);//沿着最大层检查break;caseMAX:if(x.key>h[p].key){//沿着最大层检查h[n]=h[p];VerifyMax(p,x);}elseVerifyMin(n,x);//沿着最小层检查}//switch结束}//Insert结束函数level确定一个结点是位于最小最大堆的最小层，还是位于最大层当log2(j+1)为偶数时，结点j位于最大层，否则位于最小层templatevoidMinMaxHeap::VerifyMax(inti,constElement&x){//沿着从最大结点i//到根结

4、点的路径检查最大结点，将x插入正确位置for(intgp=i/4;gp&&(x.key>h[gp].key);gp/=4){//gp是i的祖父h[i]=h[gp];//将h[gp]移到h[i]i=gp;}h[i]=x;//将x插入结点i}函数VerifyMax从最大结点i开始，沿着从结点i到最小最大堆的根的路径检查最大结点，查找插入元素x的正确结点。在查找过程中，key值小于x.key的元素被移到下一个最大层函数VerifyMin与VerifyMax类似，所不同的是，前者从最小结点i开始，沿着从结点i到根的路径检查最小结点，将元素x插入正确位置。分析：由于n个元素的最小最大堆有O(logn

5、)层，成员函数Insert的时间复杂性是O(logn)。Min-MaxHeap中刪除最小结点1.2.3.Min-maxheap假設已存在一棵min-maxheap如下：4050191310153228343118545minmaxminmax刪除45Min-maxheap(con.t)40501913101532283431185minmaxminmax刪除40則需以最後一個節點的鍵值18取代40Min-maxheap(con.t)minmaxminmax185019131015322834315交換後18<19，不符合第一項定義，將18與19交換Min-maxheap(con.t)min

6、maxminmax195018131015322834315交換後，由於19小於32、28、34、31，不符合第三項定義，將19與最大的鍵值34交換Min-maxheap(con.t)minmaxminmax345018131015322819315一般而言，将元素x插入根结点为空的最小最大堆h中有两种情况需要考虑：（1）根结点无子女，这时可将x插入根结点中。（2）根结点至少有一个子女。这时堆中的最小元素（不算元素x）位于根结点的子女结点或孙子女结点（最多6个）之一。假设该结点的编号为k，则还需要考虑下列可能性：(a)x.key≤h[k].key。由于h中不存在比x更小的元素，所以x可插入

7、根。(b)x.key>h[k].key且k是根的子女。由于k是最大结点，其后代的key值都不大于h[k].key，因而也不大于x.key。所以可将元素h[k]移到根，并将元素x插入结点k。(c)x.key>h[k].key且k是根的孙子女。这时也可将元素h[k]移到根。设p是k的双亲。若x.key>h[p].key，则将x和h[p]交换。这时，问题转化为将x插入以k为根的子堆中，且h[k]已腾空。这与初始插入根结点为空的