在计算机科学中，双端优先队列（double-ended priority queue，DEPQ）或双端堆（double-ended heap）是一个类似于优先队列或堆的数据结构，但允许根据数据结构中的键对最大值和最小值进行高效的删除操作，即可以对元素按升序或降序删除。每个元素均有一个优先级或值。

操作
一个双端优先队列有如下操作：
;isEmpty()：双端优先队列为空时返回true。
;size()：返回双端优先队列中存在的元素个数。
;getMin()：返回双端优先队列中优先级最低的元素。
;getMax()：返回双端优先队列中优先级最高的元素。
;put(x)：将元素 x 插入到双端优先队列。
;removeMin()：移除双端优先队列中优先级最低的元素，并将其返回。
;removeMax()：移除双端优先队列中优先级最高的元素，并将其返回。

如果一个操作适用于优先级相同的多个元素，那么会选择最先插入的那个元素。任何已经被插入到双端优先队列的元素的优先级也可以更改。

实现
双端优先队列可以使用平衡二叉搜索树（优先级最大和最小的元素分别是最左、最右叶子节点）构建，也可以使用特殊的数据结构，如最大—最小堆和配对堆。

从普通优先队列变为双端优先队列的一般方法是：

对偶结构方法
，其中每个节点包含两个元素（节点的左元素和右元素）。它是一棵完全二叉树，其中：

• 每个节点的左元素小于或等于右元素。
• 这两个元素共同定义了一个闭区间。
• 除根节点外的任何节点所表示的区间都是父节点的子区间。
• 节点左元素定义了一个最小堆。
• 节点右元素定义了一个最大堆。

根据元素的数量，可能有两种情况——

偶数个元素： 在这种情况下，每个节点包含两个元素，例如p和q，其中p ≤ q。每个节点由区间 [p , q] 表示。

奇数个元素： 在这种情况下，除了最后一个节点，每个节点都包含两个元素，表示区间 [ p , q ]， 而最后一个节点包含一个元素，表示区间 [ p ,  p ]。

插入一个元素
根据区间堆中已经存在的元素数量，可能有以下情况：

• 奇数个元素：如果区间堆的元素个数为奇数，则新元素先插入最后一个节点。然后，将其与之前的节点元素连续进行比较并进行测试，以满足上述间隔堆的基本标准。如果元素不满足任一条条件，则将其从最后一个节点移动到根节点，直到满足所有条件。
• 偶数个元素： 如果元素个数是偶数，则为插入新元素创建一个新节点。如果元素落在父区间的左侧，则认为它在最小堆中，如果元素落在父区间的右侧，则认为它在最大堆中。再依次比较，从最后一个节点移到根节点，直到满足区间堆的所有条件。如果元素位于父节点本身的区间内，则该过程停止，并且不会发生元素的移动。

插入元素所需的时间取决于满足所有条件所需的移动次数，为 O(log n)。

删除一个元素
*最小元素： 在区间堆中，最小元素是根节点的左元素。删除该元素并返回。为了填补根节点左元素的空缺，最后一个节点的一个元素被删除（如果最后一个节点为空，则删除最后一个节点）并重新插入根节点。然后将该元素自上往下与节点的左元素依次比较，当满足区间堆的所有条件时，过程停止。如果节点中的左元素在某个阶段大于右元素，则交换两个元素，然后进行进一步的比较。最后，根节点将再次包含整棵树的最小元素。
*最大元素： 在区间堆中，最大元素是根节点的右元素。删除该元素并返回。为了填补根节点右元素的空缺，最后一个节点的一个元素被删除（如果最后一个节点为空，则删除最后一个节点）并重新插入根节点。然后进行与删除最小元素类似的操作。最后，根节点将再次包含整棵树的最大元素。

因此，使用区间堆，可以高效地从根节点到叶节点遍历最小和最大元素。因此，一个双端优先队列可以从区间堆得到。

时间复杂度
区间堆
当用n 个元素组成的区间堆实现 DEPQ时，各种函数的时间复杂度如下表所示。

配对堆
当使用堆或由n 个元素组成的配对堆实现 DEPQ时，下表中列出了各种函数的时间复杂度。对于配对堆，展示的是平摊复杂度。

应用
外排序
双端优先队列的一个应用是外排序。在外排序中，一次需要处理的数据量超过内存容量。准备被排序的元素起初在磁盘上，而已经排序的队列保存在内存里。如下是使用双端优先队列实现外部快速排序的步骤：

读入内部 DEPQ 能存放的尽可能多的元素。DEPQ 中的元素最终将是元素的中间组（即“基准”，pivot）。

读入其余元素。如果下一个元素≤ DEPQ 中的最小元素，则将下一个元素作为左组的一部分输出。如果下一个元素≥ DEPQ 中的最大元素，则将下一个元素作为右组的一部分输出。否则，从 DEPQ 中删除最大或最小元素（可以随机或交替进行选择）；如果删除了最大元素，则将删除的元素作为右组的一部分输出；否则，将删除的元素作为左组的一部分输出；将新输入的元素插入 DEPQ。

将 DEPQ 中的元素排序，作为中间组输出。

递归地对左组和右组排序。

参见

• 队列
• 优先队列
• 双端队列

参考资料