Template:堆运行时间

本条目中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 均摊时间。
^ 下界为 $\Omega (\log \log n)$ ，^[6]上界为 $O(2^{2{\sqrt {\log \log n}}})$ 。^[7]
^ n是较大堆的大小。

^ ^1.0 ^1.1 ^1.2 ^1.3 Cormen, Thomas H. （英语：Thomas H. Cormen）; Leiserson, Charles E. （英语：Charles E. Leiserson）; Rivest, Ronald L. Introduction to Algorithms 1st. MIT Press and McGraw-Hill. 1990. ISBN 0-262-03141-8.Leiserson, Charles E.（英语：-{Charles E. Leiserson}-）&rft.au=Cormen, Thomas H.（英语：-{Thomas H. Cormen}-）&rft.au=Rivest, Ronald L.&rft.btitle=Introduction to Algorithms&rft.date=1990&rft.edition=1st&rft.genre=book&rft.isbn=0-262-03141-8&rft.pub=MIT Press and McGraw-Hill&rft_val_fmt=info:ofi/fmt:kev:mtx:book" class="Z3988">
^ 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.

[brodal-6] Brodal和Okasaki后来描述了一个可持久化的变种，拥有同样的运行上界，但不支持decrease-key。带有n个元素的堆可以在O(n)时间内从下至上构建。^[5]

[amortized-7] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 均摊时间。

[pairingdecreasekey-10] 下界为 $\Omega (\log \log n)$ ，^[6]上界为 $O(2^{2{\sqrt {\log \log n}}})$ 。^[7]

[merge-11] 是较大堆的大小。

[CLRS-1] 1.0 ^1.1 ^1.2 ^1.3 Cormen, Thomas H. （英语：Thomas H. Cormen）; Leiserson, Charles E. （英语：Charles E. Leiserson）; Rivest, Ronald L. Introduction to Algorithms 1st. MIT Press and McGraw-Hill. 1990. ISBN 0-262-03141-8.Leiserson, Charles E.（英语：-{Charles E. Leiserson}-）&rft.au=Cormen, Thomas H.（英语：-{Thomas H. Cormen}-）&rft.au=Rivest, Ronald L.&rft.btitle=Introduction to Algorithms&rft.date=1990&rft.edition=1st&rft.genre=book&rft.isbn=0-262-03141-8&rft.pub=MIT Press and McGraw-Hill&rft_val_fmt=info:ofi/fmt:kev:mtx:book" class="Z3988">

[Fredman_And_Tarjan-2] 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-3] 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] Brodal, Gerth S., Worst-Case Efficient Priority Queues (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms: 52–58, 1996

[5] 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.

[Fredman1999-8] 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.

[9] 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.

[1]

[2]

[3]

[4]

[a]

[b]

[c]

[d]

[5]

[6]

[7]