双端优先队列

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

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

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

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

从普通优先队列变为双端优先队列的一般方法是：Fundamentals of Data Structures in C++ - Ellis Horowitz, Sartaj Sahni and Dinesh Mehta

对偶结构方法
这种方法维护了两个最大和最小优先队列。使用指针可以关联两个优先队列中的相同元素。
这里，最小和最大元素分别是最小堆和最大堆的根节点中的值。
移除最小元素：对最小PQ进行 removemin() ，对最大PQ进行 remove(节点值)，其中 节点值 是最大PQ中对应节点的值。
移除最大元素：对最大PQ进行 removemax() ，对最小PQ进行 remove(节点值)，其中 节点值 是最小PQ中对应节点的值。

完全对应
一半的元素在最小PQ中，另一半在最大 PQ 中。最小PQ 中的每个元素都与 最大PQ 中的一个元素一一对应。如果 DEPQ 中的元素数量为奇数，则其中一个元素保留在缓冲区中。  最小PQ 中每个元素的优先级将小于或等于最大PQ 中的相应元素。

叶节点对应
在该方法中，只有最小PQ和最大PQ的叶元素形成一一对应。非叶元素不一定是一一对应的。

区间堆
除了上面提到的对应方法之外，使用区间堆可以高效地得到 DEPQ。 区间堆就像一个嵌入的最大-最小堆，其中每个节点包含两个元素（节点的左元素和右元素）。它是一棵完全二叉树，其中：
 每个节点的左元素小于或等于右元素。
 这两个元素共同定义了一个闭区间。
 除根节点外的任何节点所表示的区间都是父节点的子区间。
 节点左元素定义了一个最小堆。
 节点右元素定义了一个最大堆。

根据元素的数量，可能有两种情况——
 偶数个元素： 在这种情况下，每个节点包含两个元素，例如p和q，其中p ≤ q。每个节点由区间 [p , q] 表示。
 奇数个元素： 在这种情况下，除了最后一个节点，每个节点都包含两个元素，表示区间 [ p , q ]， 而最后一个节点包含一个元素，表示区间 [ p ,  p ]。

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

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

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

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

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

时间复杂度 

区间堆

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

 操作  时间复杂度 init( ) O(n) isEmpty( )  O(1) getmin( )  O(1) getmax( )  O(1) size( )  O(1) insert(x)  O(log n)  removeMin( )  O(log n)  removeMax( )  O(log n) 

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

 操作 时间复杂度 isEmpty( )  O(1) getmin( )  O(1) getmax( )  O(1) insert(x)  O(log n) removeMax( )  O(log n) removeMin( )  O(log n)

 应用

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

 读入内部 DEPQ 能存放的尽可能多的元素。DEPQ 中的元素最终将是元素的中间组（即“基准”，pivot）。
 读入其余元素。如果下一个元素≤ DEPQ 中的最小元素，则将下一个元素作为左组的一部分输出。如果下一个元素≥ DEPQ 中的最大元素，则将下一个元素作为右组的一部分输出。否则，从 DEPQ 中删除最大或最小元素（可以随机或交替进行选择）；如果删除了最大元素，则将删除的元素作为右组的一部分输出；否则，将删除的元素作为左组的一部分输出；将新输入的元素插入 DEPQ。
 将 DEPQ 中的元素排序，作为中间组输出。
 递归地对左组和右组排序。

 参见 
 队列
 优先队列
 双端队列

 参考资料

Category:抽象数据类型
Category:优先队列