最小最大堆解析ppt课件.ppt

《最小最大堆解析ppt课件.ppt》由会员分享，可在线阅读，更多相关《最小最大堆解析ppt课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、高级数据结构最小最大堆Min-Max Heap双端优先队列双端优先队列 与与 最小最大堆最小最大堆双端优先队列双端优先队列是一种支持下列操作的数据结构：是一种支持下列操作的数据结构：（1） 插入一个具有任意插入一个具有任意key值的元素值的元素（2） 删除删除key值最大的元素值最大的元素（3） 删除删除key值最小的元素值最小的元素 当只需要支持两个删除操作之一时当只需要支持两个删除操作之一时采用最小堆或最大堆采用最小堆或最大堆 支持以上全部操作支持以上全部操作最小最大堆最小最大堆 定义：最小最大堆定义：最小最大堆是一棵完全二叉树，且其中每是一棵完全二叉树，且其中每个元素有一个个元素有一个k

2、ey数据成员。树的各层交替为最小数据成员。树的各层交替为最小层和最大层。根结点在最小层。设层和最大层。根结点在最小层。设x是最小最大堆是最小最大堆的任意结点。若的任意结点。若x在最小（最大）层上，则在最小（最大）层上，则x中的元中的元素的素的key值在以值在以x为根的子树的所有元素中是最小为根的子树的所有元素中是最小（最大）的。位于最小（最大）层的结点称为（最大）的。位于最小（最大）层的结点称为最小最小（最大）结点（最大）结点。Min-Max Heap n依序插入10和801.2. 3. 4.5.新節點80位於max level且大於其父節點12，故不交換。 6. template void

3、MinMaxHeap:Insert(const Element&x ) if (n = MaxSize ) MinMaxFull( ); return; n+; int p = n/2; / p是新结点的双亲 if (!p) h1 = x; return; / 插入初始时为空的堆 switch (level(p) case MIN: if (x.key hp.key) / 沿着最大层检查 hn=hp; VerifyMax(p, x); else VerifyMin(n, x); / 沿着最小层检查 / switch结束 / Insert结束 函数函数level确定一个结点是位于最小最大堆的最小

4、确定一个结点是位于最小最大堆的最小层，还是位于最大层层，还是位于最大层当当 log2(j + 1) 为偶数时，结点为偶数时，结点j位于最大层，位于最大层，否则位于最小层否则位于最小层 template void MinMaxHeap:VerifyMax (int i, const Element&x ) / 沿着从最大结点i / 到根结点的路径检查最大结点，将x插入正确位置 for (int gp = i/4; gp & (x.key hgp.key); gp /=4) / gp是 i的祖父 hi = hgp;/ 将hgp移到hi i = gp; hi = x; / 将x插入结点i 函数函数V

5、erifyMax从最大结点从最大结点i开始，沿着从结点开始，沿着从结点i到最到最小最大堆的根的路径检查最大结点，查找插入元素小最大堆的根的路径检查最大结点，查找插入元素x的正确结点。在查找过程中，的正确结点。在查找过程中，key值小于值小于x.key的元的元素被移到下一个最大层素被移到下一个最大层 函数函数VerifyMin与与VerifyMax类似，所不同的是，类似，所不同的是，前者从最小结点前者从最小结点i开始，沿着从结点开始，沿着从结点i到根的路径检到根的路径检查最小结点，将元素查最小结点，将元素x插入正确位置。插入正确位置。 分析：分析：由于由于n个元素的最小最大堆有个元素的最小最大堆

6、有O(log n)层，层，成员函数成员函数Insert的时间复杂性是的时间复杂性是O(log n)。nMin-Max Heap中刪除最小结点1.2.3.Min-max heapn假設已存在一棵min-max heap如下： 4050191310153228343118545minmaxmin max q刪除45Min-max heap (con.t)40501913101532283431185minmaxmin max q刪除40n則需以最後一個節點的鍵值18取代40Min-max heap (con.t)minmaxmin max 185019131015322834315q交換後18 h

7、k.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已腾空。这与初始已腾空。这与初始插入根结点为空的最小

8、最大堆插入根结点为空的最小最大堆h的情形类似。的情形类似。 通过以上讨论，可得成员函数通过以上讨论，可得成员函数DeleteMin。template Element* MinMaxHeap: DeleteMin(Element&y) / 从最小最大堆中删除并返回最小元素 if (!n) MinMaxEmpty( ); return 0; y = h1; / 保存根元素 Element x = hn-; int i = 1, j = n/2; / 为重新插入x作初始化 / 寻找插入x的位置 while (i = j) / i 有子女，情况(2) int k = MinChildGrandChil

9、d(i); if (x.key = hk.key) break;/ 情况 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 &y; 其中又用到私有成员函数其中又用到私有成员函数MinChildGrandChild(i)，该函数返回结点该函数返回结点i的子女结点

10、或孙子女结点中含最小的子女结点或孙子女结点中含最小元素的结点。元素的结点。 如果如果i的子女结点或孙子女结点都含最小元素，的子女结点或孙子女结点都含最小元素，则则MinChildGrandChild返回子女结点，这样可以避返回子女结点，这样可以避免免DeleteMin中中while循环的进一步迭代。循环的进一步迭代。 分析：分析：while循环的每次迭代需循环的每次迭代需O(1)时间，且每经时间，且每经过一次迭代（可能除了最后一次以外），过一次迭代（可能除了最后一次以外），i都下移两都下移两层。由于层。由于n个元素的最小最大堆有个元素的最小最大堆有O(log n)层，层，DeleteMin的时间复杂性是的时间复杂性是O(log n)。 删除最大元素的过程与删除最小元素类似。删除最大元素的过程与删除最小元素类似。