双端优先队列

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

操作

一个双端优先队列有如下操作:

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

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

实现

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

从普通优先队列变为双端优先队列的一般方法是:[5]

对偶结构方法

 
一个对偶结构,以14,12,4,10,8作为双端优先队列的成员。[1]

这种方法维护了两个最大和最小优先队列。使用指针可以关联两个优先队列中的相同元素。
这里,最小和最大元素分别是最小堆和最大堆的根节点中的值。

  • 移除最小元素:对最小PQ进行 removemin() ,对最大PQ进行 remove(节点值),其中 节点值 是最大PQ中对应节点的值。
  • 移除最大元素:对最大PQ进行 removemax() ,对最小PQ进行 remove(节点值),其中 节点值 是最小PQ中对应节点的值。

完全对应

 
由3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11构成的完全对应堆。元素11在缓冲区中。[1]

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

叶节点对应

 
由上图相同元素组成的叶节点对应堆。[1]

在该方法中,只有最小PQ和最大PQ的叶元素形成一一对应。非叶元素不一定是一一对应的。[1]

区间堆

 
使用区间堆实现双端优先队列。

除了上面提到的对应方法之外,使用区间堆可以高效地得到 DEPQ。[6] 区间堆就像一个嵌入的最大-最小堆,其中每个节点包含两个元素(节点的左元素和右元素)。它是一棵完全二叉树,其中:[6]

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

根据元素的数量,可能有两种情况[6]——

  1. 偶数个元素: 在这种情况下,每个节点包含两个元素,例如pq,其中pq。每个节点由区间 [p , q] 表示。
  2. 奇数个元素: 在这种情况下,除了最后一个节点,每个节点都包含两个元素,表示区间 [ 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)

应用

外排序

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

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

参见

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

参考资料

  1. ^ 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.
  2. ^ Brass, Peter. Advanced Data Structures. Cambridge University Press. 2008: 211. ISBN 9780521880374. 
  3. ^ Depq - Double-Ended Priority Queue. [2011-10-04]. (原始内容存档于2012-04-25). 
  4. ^ depq. [2021-11-13]. (原始内容存档于2022-01-20). 
  5. ^ Fundamentals of Data Structures in C++ - Ellis Horowitz, Sartaj Sahni and Dinesh Mehta
  6. ^ 6.0 6.1 6.2 6.3 6.4 6.5 6.6 存档副本 (PDF). [2021-11-13]. (原始内容存档 (PDF)于2018-11-23).