双端优先队列(DEPQ)

双端优先级队列(DEPQ)或双端堆被定义为类似于优先级队列或堆的数据结构，但可以根据存储在其中的键或项的某些顺序有效地除去最大值和最小值结构。DEPQ中与优先级或值关联的每个元素。在DEPQ中，可以按升序和降序删除或删除元素。

运作方式

双优先级队列由以下操作组成

是空的()

该函数负责检查DEPQ是否为空，如果为空，则返回true。

尺寸()

该函数负责返回DEPQ中存在的元素总数。

getMin(y)

该函数负责返回优先级最低的元素y。

getMax(y)

该函数负责返回优先级最高的元素y。

放(y)

该函数负责将元素y插入DEPQ。

removeMin(y)

该函数负责删除优先级最低的元素y并返回该元素。

removeMax(y)

该函数负责删除具有最高优先级的元素y并返回该元素。

实作

双端优先级队列可以由平衡的二叉搜索树（其中最小和最大的元素分别被视为最左边和最右边的叶子）构建或形成，或实现特殊的数据结构（如最小-最大堆和配对堆）。

从普通优先级队列到达双端优先级队列的一般方法是：

根据此方法，设置或维护两个不同的min和max优先级队列。两个优先级队列中的相同元素在对应指针的帮助下显示或显示。

在此，最小和最大元素分别表示为最小堆和最大堆的根节点中包含的值。

删除最小元素-removemin()在最小堆上操作并在最大堆上删除（节点值），其中节点值定义为最大堆中相应节点中的值。

删除最大元素-removemax()在最大堆上操作，在最小堆上删除（节点值），其中节点值定义为最小堆中相应节点中的值。

元素的一半在最小优先级队列中，另一半在最大优先级队列中。最小优先级队列中的每个元素与最大优先级队列中的元素具有一一对应关系。如果DEPQ中的元素数量指示为奇数值，则将元素之一保留在缓冲区（即特定存储区域）中。最小优先级队列中每个元素的优先级将小于或等于最大优先级队列中相应的元素。

根据此方法，只有最小和最大优先级队列的叶元素形成相应的一对一对。非叶元素不需要一对一对应。

除上述对应方法外，还可以完美地实现间隔堆来获得DEPQ。间隔堆就像嵌入式的最小-最大堆，其中每个节点都由两个元素组成。它被定义为一个完整的二叉树，其中-