问题描述

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

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

解决方案

参考：http://blog.chinaunix.net/uid-20357359-id-1963209.html