双端优先队列
在计算机科学中，双端优先队列（double-ended priority queue，DEPQ）[1]或双端堆（double-ended heap）[2]是一个类似于优先队列或堆的数据结构，但允许根据数据结构中的键对最大值和最小值进行高效的删除操作，即可以对元素按升序或降序删除。每个元素均有一个优先级或值。[3]
操作
[编辑]一个双端优先队列有如下操作：
- isEmpty()：双端优先队列为空时返回true。
- size()：返回双端优先队列中存在的元素个数。
- getMin()：返回双端优先队列中优先级最低的元素。
- getMax()：返回双端优先队列中优先级最高的元素。
- put(x)：将元素 x 插入到双端优先队列。
- removeMin()：移除双端优先队列中优先级最低的元素，并将其返回。
- removeMax()：移除双端优先队列中优先级最高的元素，并将其返回。
如果一个操作适用于优先级相同的多个元素，那么会选择最先插入的那个元素。任何已经被插入到双端优先队列的元素的优先级也可以更改。[4]
实现
[编辑]双端优先队列可以使用平衡二叉搜索树（优先级最大和最小的元素分别是最左、最右叶子节点）构建，也可以使用特殊的数据结构，如最大—最小堆和配对堆。
从普通优先队列变为双端优先队列的一般方法是：[5]
对偶结构方法
[编辑]
这种方法维护了两个最大和最小优先队列。使用指针可以关联两个优先队列中的相同元素。
这里，最小和最大元素分别是最小堆和最大堆的根节点中的值。
- 移除最小元素：对最小PQ进行 removemin() ，对最大PQ进行 remove(节点值)，其中 节点值 是最大PQ中对应节点的值。
- 移除最大元素：对最大PQ进行 removemax() ，对最小PQ进行 remove(节点值)，其中 节点值 是最小PQ中对应节点的值。
完全对应
[编辑]
一半的元素在最小PQ中，另一半在最大 PQ 中。最小PQ 中的每个元素都与 最大PQ 中的一个元素一一对应。如果 DEPQ 中的元素数量为奇数，则其中一个元素保留在缓冲区中。[1] 最小PQ 中每个元素的优先级将小于或等于最大PQ 中的相应元素。
叶节点对应
[编辑]
在该方法中，只有最小PQ和最大PQ的叶元素形成一一对应。非叶元素不一定是一一对应的。[1]
区间堆
[编辑]
除了上面提到的对应方法之外，使用区间堆可以高效地得到 DEPQ。[6] 区间堆就像一个嵌入的最大-最小堆，其中每个节点包含两个元素（节点的左元素和右元素）。它是一棵完全二叉树，其中：[6]
根据元素的数量，可能有两种情况[6]——
- 偶数个元素： 在这种情况下，每个节点包含两个元素，例如p和q，其中p ≤ q。每个节点由区间 [p , q] 表示。
- 奇数个元素： 在这种情况下，除了最后一个节点，每个节点都包含两个元素，表示区间 [ p , q ]， 而最后一个节点包含一个元素，表示区间 [ p , p ]。
插入一个元素
[编辑]根据区间堆中已经存在的元素数量，可能有以下情况：
- 奇数个元素：如果区间堆的元素个数为奇数，则新元素先插入最后一个节点。然后，将其与之前的节点元素连续进行比较并进行测试，以满足上述间隔堆的基本标准。如果元素不满足任一条条件，则将其从最后一个节点移动到根节点，直到满足所有条件。[6]
- 偶数个元素： 如果元素个数是偶数，则为插入新元素创建一个新节点。如果元素落在父区间的左侧，则认为它在最小堆中，如果元素落在父区间的右侧，则认为它在最大堆中。再依次比较，从最后一个节点移到根节点，直到满足区间堆的所有条件。如果元素位于父节点本身的区间内，则该过程停止，并且不会发生元素的移动。[6]
插入元素所需的时间取决于满足所有条件所需的移动次数，为 O(log n)。
删除一个元素
[编辑]- 最小元素： 在区间堆中，最小元素是根节点的左元素。删除该元素并返回。为了填补根节点左元素的空缺，最后一个节点的一个元素被删除（如果最后一个节点为空，则删除最后一个节点）并重新插入根节点。然后将该元素自上往下与节点的左元素依次比较，当满足区间堆的所有条件时，过程停止。如果节点中的左元素在某个阶段大于右元素，则交换两个元素[6]，然后进行进一步的比较。最后，根节点将再次包含整棵树的最小元素。
- 最大元素： 在区间堆中，最大元素是根节点的右元素。删除该元素并返回。为了填补根节点右元素的空缺，最后一个节点的一个元素被删除（如果最后一个节点为空，则删除最后一个节点）并重新插入根节点。然后进行与删除最小元素类似的操作。最后，根节点将再次包含整棵树的最大元素。
因此，使用区间堆，可以高效地从根节点到叶节点遍历最小和最大元素。因此，一个双端优先队列可以从区间堆得到[6]。
时间复杂度
[编辑]区间堆
[编辑]当用n 个元素组成的区间堆实现 DEPQ时，各种函数的时间复杂度如下表所示。[1]
| 操作 | 时间复杂度 |
|---|---|
| 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时，下表中列出了各种函数的时间复杂度。[1]对于配对堆，展示的是平摊复杂度。
| 操作 | 时间复杂度 |
|---|---|
| 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 中的元素排序，作为中间组输出。
- 递归地对左组和右组排序。
参见
[编辑]参考资料
[编辑]- ^ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 Data Structures, Algorithms, & Applications in Java: Double-Ended Priority Queues （页面存档备份，存于互联网档案馆）, Sartaj Sahni, 1999.
- ^ Brass, Peter. Advanced Data Structures. Cambridge University Press. 2008: 211. ISBN 9780521880374.
- ^ Depq - Double-Ended Priority Queue. [2011-10-04]. （原始内容存档于2012-04-25）.
- ^ depq. [2021-11-13]. （原始内容存档于2022-01-20）.
- ^ Fundamentals of Data Structures in C++ - Ellis Horowitz, Sartaj Sahni and Dinesh Mehta
- ^ 6.0 6.1 6.2 6.3 6.4 6.5 6.6 存档副本 (PDF). [2021-11-13]. （原始内容存档 (PDF)于2018-11-23）.