2 ss1221yy ss1221yy 于 2016.02.13 19:44 提问

如何用大小根交替堆实现双端优先队列?

双端优先队列是一个支持如下操作的数据结构:
•Insert (S, x) – 将元素x插入集合S
•Extract –Min (S) –删除S中的最小关键字
•Extract –Max (S) –删除S中的最大关键字
可用小大根交替堆来实现对上述三个操作的支持。小大根交替堆是一个满足如下小大根交替条件的完全二元树:如果该二元树不空,那么其上的每个元素都有一个称为关键字的域,且针对该关键字,二元树按层次形成了小大根交替的形式,即对于小大根交替堆中的任何一个结点x,如果x位于小根层次,那么x就是以x为根节点的二元树中键值最小的结点,并称该结点为一个小根结点。同样的道理,如果x位于大根层次,那么x就是以x为根节点的二元树中键值最大的结点,并称该结点为一个大根结点。在小大根交替堆中根结点位于小根层次。

1个回答

caozhy
caozhy   Ds   Rxr 2016.02.13 21:48
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!