双端优先队列
在计算机科学中,双端优先队列(double-ended priority queue,DEPQ)[1]或双端堆(double-ended heap)[2]是一个类似于优先队列或堆的数据结构,但允许根据数据结构中的键对最大值和最小值进行高效的删除操作,即可以对元素按升序或降序删除。每个元素均有一个优先级或值。[3]
操作
一个双端优先队列有如下操作:
- isEmpty():双端优先队列为空时返回true。
- size():返回双端优先队列中存在的元素个数。
- getMin():返回双端优先队列中优先级最低的元素。
- getMax():返回双端优先队列中优先级最高的元素。
- put(x):将元素 x 插入到双端优先队列。
- removeMin():移除双端优先队列中优先级最低的元素,并将其返回。
- removeMax():移除双端优先队列中优先级最高的元素,并将其返回。
如果一个操作适用于优先级相同的多个元素,那么会选择最先插入的那个元素。任何已经被插入到双端优先队列的元素的优先级也可以更改。[4]
实现
双端优先队列可以使用平衡二叉搜索树(优先级最大和最小的元素分别是最左、最右叶子节点)构建,也可以使用特殊的数据结构,如最大—最小堆和配对堆。
从普通优先队列变为双端优先队列的一般方法是:[5]
对偶结构方法
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/b/b7/Dual_heap.jpg/330px-Dual_heap.jpg)
这种方法维护了两个最大和最小优先队列。使用指针可以关联两个优先队列中的相同元素。
这里,最小和最大元素分别是最小堆和最大堆的根节点中的值。
- 移除最小元素:对最小PQ进行 removemin() ,对最大PQ进行 remove(节点值),其中 节点值 是最大PQ中对应节点的值。
- 移除最大元素:对最大PQ进行 removemax() ,对最小PQ进行 remove(节点值),其中 节点值 是最小PQ中对应节点的值。
完全对应
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/2/2e/Total_correspondence_heap.jpg/330px-Total_correspondence_heap.jpg)
一半的元素在最小PQ中,另一半在最大 PQ 中。最小PQ 中的每个元素都与 最大PQ 中的一个元素一一对应。如果 DEPQ 中的元素数量为奇数,则其中一个元素保留在缓冲区中。[1] 最小PQ 中每个元素的优先级将小于或等于最大PQ 中的相应元素。
叶节点对应
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/a/a7/Leaf_correspondence.jpg/330px-Leaf_correspondence.jpg)
在该方法中,只有最小PQ和最大PQ的叶元素形成一一对应。非叶元素不一定是一一对应的。[1]
区间堆
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/e/ec/Interval_heap_depq.jpg/330px-Interval_heap_depq.jpg)
除了上面提到的对应方法之外,使用区间堆可以高效地得到 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).
|