配對堆
![]() |
此條目翻譯品質不佳。 |
配對堆 | |||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
類型 | 堆積 | ||||||||||||||||||||||||
發明時間 | 1986年 | ||||||||||||||||||||||||
發明者 | 邁克爾·弗雷德曼、羅伯特·塞奇威克、丹尼爾·斯萊托、羅伯特·塔揚 | ||||||||||||||||||||||||
用大O符號表示的時間複雜度 | |||||||||||||||||||||||||
|
配對堆(英語:Pairing heap)是一種實現簡單、均攤複雜度優越的堆數據結構,由邁克爾·弗雷德曼、羅伯特·塞奇威克、丹尼爾·斯萊托、羅伯特·塔揚於1986年發明。[1] 配對堆是一種多叉樹,並且可以被認為是一種簡化的斐波那契堆。對於實現例如普林姆最小生成樹算法等算法,配對堆是一個更優的選擇[2],且支持以下操作(假設該堆是最小堆):
- find-min(查找最小值):返回堆頂。
- merge(合併):比較兩個堆頂,將堆頂較大的堆設為另一個的孩子。
- insert(插入):創建一個只有一個元素的堆,並合併至原堆中。
- decrease-key(減小元素)(可選):將以該節點為根的子樹移除,減小其權值,並合併回去。
- delete-min(刪除最小值):刪除根並將其子樹合併至一起。這裏有各種不同的方式。
配對堆時間複雜度的分析靈感來源於伸展樹。[1] 其delete-min操作的時間複雜度為O(log n),而find-min、merge和insert操作的均攤時間複雜度均為O(1)。[3]
確定配對堆每次進行decrease-key操作的均攤時間複雜度是困難的。最初,基於經驗,這個操作的時間複雜度被推測為是O(1),[4]但弗雷德曼證明了對於某些操作序列,每次decrease-key操作的時間複雜度至少為。[5] 在那之後,通過不同的均攤依據,Pettie證明了insert、merge及decrease-key操作的均攤時間複雜度均為,近似於。[6] Elmasry後來介紹了一種配對堆的變體,令其擁有所有斐波那契堆可以實現的操作,且decrease-key操作的均攤時間複雜度為,[7]但對於原始的數據結構,仍未知準確的運行下限。[6][3]此外,能否使delete-min在均攤時間複雜度為的同時,令insert操作的均攤時間複雜度為,目前也仍未得到解決。[8]
儘管這比其他的,例如能實現均攤時間的decrease-key的斐波那契堆,這樣的優先隊列算法更差,在實踐中配對堆的表現仍然很不錯。Stasko和Vitter,[4] Moret和Shapiro,[9] 以及Larkin、Sen和Tarjan[8] 進行過配對堆和其他堆數據結構的實驗。 他們得出的結論是, 配對堆通常比基於數組的二叉堆和D叉堆的實際操作速度更快,而且在實踐中幾乎總是比其他基於指針的堆更快,其中包括諸如斐波納契堆這樣的理論上更有效率的數據結構。
結構
一個配對堆要麼是一個空堆,要麼就是一個配對樹,由一個根元素與一個可能為空的配對樹列表所組成。堆的有序屬性使該列表中所有子樹的根元素都不小於該堆的根元素。下面描述了一個純粹的函數堆,我們假定它不支持decrease-key操作。
type PairingTree[Elem] = Heap(elem: Elem, subheaps: List[PairingTree[Elem]]) type PairingHeap[Elem] = Empty | PairingTree[Elem]
對於隨機存取機,一個基於指針的實現若要支持decrease-key操作,可以對每個節點使用三個指針做到,具體做法是用單向鍊表儲存節點的孩子:一個指針指向該節點的第一個孩子,一個指向它的下個兄弟,一個指向它的上個兄弟(對於最左邊的兄弟則指向它的父親)。或者,如果使用一個布爾標記表示「鍊表末尾」且令最後一個孩子指向它的父親,指向上個兄弟的指針也可以不使用。這在犧牲常數開銷的同時,令結構更加緊湊。[1]
操作
find-min(查找最小值)
函數find-min簡單地返回該堆的堆頂:
function find-min(heap: PairingHeap[Elem]) -> Elem if heap is Empty error else return heap.elem
merge(合併)
合併一個空堆將會返回另一個堆,否則將會返回一個新堆,其將兩個堆的根元素中較小的元素當作新堆的根元素,並將較大的元素所在的堆合併到新堆的子堆中:
function merge(heap1, heap2: PairingHeap[Elem]) -> PairingHeap[Elem] if heap1 is Empty return heap2 elsif heap2 is Empty return heap1 elsif heap1.elem < heap2.elem return Heap(heap1.elem, heap2 :: heap1.subheaps) else return Heap(heap2.elem, heap1 :: heap2.subheaps)
insert(插入)
插入一個元素最簡單的方法是,將一個僅有該元素的新堆與需要被插入的堆合併:
function insert(elem: Elem, heap: PairingHeap[Elem]) -> PairingHeap[Elem] return merge(Heap(elem, []), heap)
delete-min(刪除最小值)
唯一比較複雜的操作即是堆中最小值的刪除操作。標準方法是:首先將子堆從左到右、一對一對地合併(這就是它叫這個名字的原因),然後再從右到左合併該堆。
function delete-min(heap: PairingHeap[Elem]) -> PairingHeap[Elem] if heap is Empty error else return merge-pairs(heap.subheaps)
這需要使用到輔助函數merge-pairs(合併對):
function merge-pairs(list: List[PairingTree[Elem]]) -> PairingHeap[Elem] if length(list) == 0 return Empty elsif length(list) == 1 return list[0] else return merge(merge(list[0], list[1]), merge-pairs(list[2..]))
這確實實現了所描述的兩個通過從左向右、然後從右向左的合併策略。這可以下面的過程看到:
merge-pairs([H1, H2, H3, H4, H5, H6, H7]) => merge(merge(H1, H2), merge-pairs([H3, H4, H5, H6, H7])) # 合并H1和H2到H12,再处理列表中剩下的部分 => merge(H12, merge(merge(H3, H4), merge-pairs([H5, H6, H7]))) # 合并H3和H4到H34,再处理列表中剩下的部分 => merge(H12, merge(H34, merge(merge(H5, H6), merge-pairs([H7])))) # 合并H5和H6到H56,再处理列表中剩下的部分 => merge(H12, merge(H34, merge(H56, H7))) # 转换方向,合并最后两个堆,给出H567 => merge(H12, merge(H34, H567)) # 合并最后两个堆,给出H34567 => merge(H12, H34567) # 最终,合并第一个堆和剩下堆合并的结果 => H1234567
運行時間統計
下面的時間複雜度中,[10]O(f)是一個漸近的上界,而Θ(f)是一個準確的上界(見大O符號)。函數名均假設該堆為最小堆。
操作 | 二叉[10] | 左偏 | 二項[10] | 斐波那契[10][11] | 配對[3] | Brodal[12][a] |
---|---|---|---|---|---|---|
find-min | Θ(1) | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) |
delete-min | Θ(log n) | Θ(log n) | Θ(log n) | O(log n)[b] | O(log n)[b] | O(log n) |
insert | O(log n) | Θ(log n) | Θ(1)[b] | Θ(1) | Θ(1) | Θ(1) |
decrease-key | Θ(log n) | Θ(n) | Θ(log n) | Θ(1)[b] | o(log n)[b][c] | Θ(1) |
merge | Θ(n) | Θ(log n) | O(log n)[d] | Θ(1) | Θ(1) | Θ(1) |
參考文獻
- ^ 1.0 1.1 1.2 Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. The pairing heap: a new form of self-adjusting heap (PDF). Algorithmica. 1986, 1 (1): 111–129 [2018-04-13]. doi:10.1007/BF01840439. (原始內容存檔 (PDF)於2021-05-06).
- ^ Mehlhorn, Kurt; Sanders, Peter. Algorithms and Data Structures: The Basic Toolbox (PDF). Springer. 2008: 231 [2018-04-13]. (原始內容存檔 (PDF)於2019-12-31).
- ^ 3.0 3.1 3.2 Iacono, John, Improved upper bounds for pairing heaps, Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science 1851, Springer-Verlag: 63–77, 2000, ISBN 3-540-67690-2, arXiv:1110.4428
, doi:10.1007/3-540-44985-X_5
- ^ 4.0 4.1 Stasko, John T.; Vitter, Jeffrey S., Pairing heaps: experiments and analysis (PDF), Communications of the ACM, 1987, 30 (3): 234–249 [2018-05-20], CiteSeerX 10.1.1.106.2988
, doi:10.1145/214748.214759, (原始內容存檔 (PDF)於2017-08-29)
- ^ Fredman, Michael L. On the efficiency of pairing heaps and related data structures (PDF). Journal of the ACM. 1999, 46 (4): 473–501. doi:10.1145/320211.320214. (原始內容 (PDF)存檔於2011年7月21日).
- ^ 6.0 6.1 Pettie, Seth, Towards a final analysis of pairing heaps (PDF), Proc. 46th Annual IEEE Symposium on Foundations of Computer Science: 174–183, 2005 [2018-05-20], ISBN 0-7695-2468-0, doi:10.1109/SFCS.2005.75, (原始內容存檔 (PDF)於2012-01-28)
- ^ Elmasry, Amr, Pairing heaps with decrease cost (PDF), Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms: 471–476, 2009 [2018-05-20], CiteSeerX 10.1.1.502.6706
, doi:10.1137/1.9781611973068.52, (原始內容存檔 (PDF)於2012-10-18)
- ^ 8.0 8.1 Larkin, Daniel H.; Sen, Siddhartha; Tarjan, Robert E., A back-to-basics empirical study of priority queues, Proceedings of the 16th Workshop on Algorithm Engineering and Experiments (PDF): 61–72, 2014, CiteSeerX 10.1.1.638.5198
, arXiv:1403.0252
, doi:10.1137/1.9781611973198.7[永久失效連結]
- ^ Moret, Bernard M. E.; Shapiro, Henry D., An empirical analysis of algorithms for constructing a minimum spanning tree, Proc. 2nd Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 519, Springer-Verlag: 400–411, 1991 [2018-05-20], CiteSeerX 10.1.1.53.5960
, ISBN 3-540-54343-0, doi:10.1007/BFb0028279, (原始內容存檔於2018-07-21)
- ^ 10.0 10.1 10.2 10.3 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. Introduction to Algorithms 1st. MIT Press and McGraw-Hill. 1990. ISBN 0-262-03141-8.
- ^ Fredman, Michael Lawrence; Tarjan, Robert E. Fibonacci heaps and their uses in improved network optimization algorithms (PDF). Journal of the Association for Computing Machinery. July 1987, 34 (3): 596–615. doi:10.1145/28869.28874.
- ^ Brodal, Gerth S., Worst-Case Efficient Priority Queues (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms: 52–58, 1996
- ^ Goodrich, Michael T.; Tamassia, Roberto. 7.3.6. Bottom-Up Heap Construction. Data Structures and Algorithms in Java 3rd. 2004: 338–341. ISBN 0-471-46983-1.
- ^ Fredman, Michael Lawrence. On the Efficiency of Pairing Heaps and Related Data Structures (PDF). Journal of the Association for Computing Machinery. July 1999, 46 (4): 473–501. doi:10.1145/320211.320214.
- ^ Pettie, Seth. Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science: 174–183. 2005. CiteSeerX 10.1.1.549.471
. ISBN 0-7695-2468-0. doi:10.1109/SFCS.2005.75.
外部連結
- Louis Wasserman discusses pairing heaps and their implementation in Haskell in The Monad Reader, Issue 16 (頁面存檔備份,存於互聯網檔案館) (pp. 37–52).
- pairing heaps (頁面存檔備份,存於互聯網檔案館), Sartaj Sahni
|
|