 | 本條目中Rank-pairing堆和Strict Fibonacci的相關信息不完整。請幫忙改善本條目中Rank-pairing堆和Strict Fibonacci的相關信息，或到討論頁去討論該條目的問題。 |
下面的時間複雜度中，[1]O(f)是一個漸近的上界，而Θ(f)是一個準確的上界（見大O符號）。函數名均假設該堆為最小堆。
| 操作
|
二叉[1]
|
左偏
|
二項[1]
|
斐波那契[1][2]
|
配對[3]
|
Brodal[4][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)
|
- ^ Brodal和Okasaki後來描述了一個可持久化的變種，擁有同樣的運行上界，但不支持decrease-key。
帶有n個元素的堆可以在O(n)時間內從下至上構建。[5]
- ^ 2.0 2.1 2.2 2.3 2.4 均攤時間。
- ^ 下界為
，[6]上界為
。[7]
- ^ n是較大堆的大小。
- ^ 1.0 1.1 1.2 1.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.
- ^ 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
- ^ 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.
