《最小最大堆解析ppt课件.ppt》由会员分享，可在线阅读，更多相关《最小最大堆解析ppt课件.ppt（25页珍藏版）》请在三一办公上搜索。
1、高级数据结构最小最大堆Min-Max Heap,双端优先队列 与 最小最大堆,双端优先队列是一种支持下列操作的数据结构：（1）插入一个具有任意key值的元素（2）删除key值最大的元素（3）删除key值最小的元素 当只需要支持两个删除操作之一时采用最小堆或最大堆 支持以上全部操作最小最大堆,定义：最小最大堆是一棵完全二叉树，且其中每个元素有一个key数据成员。树的各层交替为最小层和最大层。根结点在最小层。设x是最小最大堆的任意结点。若x在最小（最大）层上，则x中的元素的key值在以x为根的子树的所有元素中是最小（最大）的。位于最小（最大）层的结点称为最小（最大）结点。,Min-Max Heap
2、,依序插入10和80,1.2.3.,4.5.新節點80位於max level且大於其父節點12，故不交換。6.,template void MinMaxHeap:Insert(const Element,else VerifyMax(n,x);/沿着最大层检查 break;case MAX:if(x.key hp.key)/沿着最大层检查 hn=hp;VerifyMax(p,x);else VerifyMin(n,x);/沿着最小层检查/switch结束/Insert结束,函数level确定一个结点是位于最小最大堆的最小层，还是位于最大层当log2(j+1)为偶数时，结点j位于最大层，否则位于
3、最小层,template void MinMaxHeap:VerifyMax(int i,const Element/将x插入结点i,函数VerifyMax从最大结点i开始，沿着从结点i到最小最大堆的根的路径检查最大结点，查找插入元素x的正确结点。在查找过程中，key值小于x.key的元素被移到下一个最大层,函数VerifyMin与VerifyMax类似，所不同的是，前者从最小结点i开始，沿着从结点i到根的路径检查最小结点，将元素x插入正确位置。分析：由于n个元素的最小最大堆有O(log n)层，成员函数Insert的时间复杂性是O(log n)。,Min-Max Heap中刪除最小结点,1.
4、2.3.,Min-max heap,假設已存在一棵min-max heap如下：,刪除45,Min-max heap(con.t),刪除40則需以最後一個節點的鍵值18取代40,Min-max heap(con.t),交換後1819，不符合第一項定義，將18與19交換,Min-max heap(con.t),交換後，由於19小於32、28、34、31，不符合第三項定義，將19與最大的鍵值34交換,Min-max heap(con.t),一般而言，将元素x插入根结点为空的最小最大堆h中有两种情况需要考虑：（1）根结点无子女，这时可将x插入根结点中。（2）根结点至少有一个子女。这时堆中的最小元素（
5、不算元素x）位于根结点的子女结点或孙子女结点（最多6个）之一。假设该结点的编号为k，则还需要考虑下列可能性：(a)x.keyhk.key。由于h中不存在比x更小的元素，所以x可插入根。,(b)x.key hk.key且k是根的子女。由于k是最大结点，其后代的key值都不大于hk.key，因而也不大于x.key。所以可将元素hk移到根，并将元素x插入结点k。(c)x.key hk.key且k是根的孙子女。这时也可将元素hk移到根。设p是k的双亲。若x.key hp.key，则将x 和hp交换。这时，问题转化为将x插入以k为根的子堆中，且hk已腾空。这与初始插入根结点为空的最小最大堆h的情形类似。
6、,通过以上讨论，可得成员函数DeleteMin。template Element*MinMaxHeap:DeleteMin(Element/情况 2(a)，可将x 插入hi,else/情况2(b)或(c)hi=hk;if(k hp.key)Element t=hp;hp=x;x=t;/if(k=2*i+1)结束 i=k;/if(x.key=hk.key)结束,/while结束 hi=x;/注意，即使现在n=0，对h1 赋值也没/错，这样简化边界判断 return 其中又用到私有成员函数MinChildGrandChild(i)，该函数返回结点i的子女结点或孙子女结点中含最小元素的结点。如果i的子女结点或孙子女结点都含最小元素，则MinChildGrandChild返回子女结点，这样可以避免DeleteMin中while循环的进一步迭代。,分析：while循环的每次迭代需O(1)时间，且每经过一次迭代（可能除了最后一次以外），i都下移两层。由于n个元素的最小最大堆有O(log n)层，DeleteMin的时间复杂性是O(log n)。删除最大元素的过程与删除最小元素类似。,
