翘首以望
2016-02-13 11:44
采纳率: 100%
浏览 2.1k

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

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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

相关推荐 更多相似问题