雙端優先隊列

計算機科學中,雙端優先隊列(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).