雙端優先隊列
在計算機科學中，雙端優先隊列（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）.
| |||||||||||||||||||||||||||||||||||||