双优先级队列

存在从单端优先级队列(PQ)数据结构导出高效DEPQ(双端优先级队列)数据结构的通用方法，这些方法也提供了高效的remove(bNode)操作的实现(此操作从PQ中删除节点bNode)。最简单的这种方法，双结构方法，同时维护一个最小PQ和一个最大PQ，其中包含DEPQ的所有元素，并在最小PQ和最大PQ的节点之间设置对应指针，这些节点包含相同的元素。

图D显示了元素7、8、3、6、5的双堆结构。对应指针显示为红色箭头。

图D：双堆

尽管图中显示每个元素都存储在最小堆和最大堆中，但实际上只需要将每个元素存储在两个堆中的一个即可。

isEmpty和size操作通过实现一个变量size来实现，该变量跟踪DEPQ中元素的数量。最小元素位于最小堆的根部，最大元素位于最大堆的根部。要插入元素B，我们将B插入最小堆和最大堆，然后在B在最小堆和最大堆中的位置之间设置对应指针。要消除最小元素，我们从最小堆中执行removeMin，并从最大堆中执行remove(bNode)，其中bNode是已删除元素的对应节点。最大元素的消除方式类似。

Arnab Chakraborty

更新于：2020年1月3日

226 次浏览

开启你的职业生涯

通过完成课程获得认证

开始