查看“︁Template:堆运行时间”︁的源代码

<noinclude>{{Incomplete|条目中Rank-pairing堆和Strict Fibonacci的相关信息}}</noinclude>
下面的[[计算复杂性理论|时间复杂度]]中，<ref name="CLRS">{{Introduction to Algorithms|edition=1}}</ref>''O''(''f'')是一个渐近的上界，而''Θ''(''f'')是一个准确的上界（见[[大O符号]]）。函数名均假设该堆为最小堆。

{|  class="wikitable"
|-
! 操作
! [[二叉堆|二叉]]<ref name="CLRS"/>
! [[左偏树|左偏]]
! [[二项堆|二项]]<ref name="CLRS"/>
! [[斐波那契堆|斐波那契]]<ref name="CLRS"/><ref name="Fredman And Tarjan">{{cite journal
 |first1=Michael Lawrence |last1=Fredman |authorlink1=Michael Fredman
 |first2=Robert E. |last2=Tarjan |authorlink2=Robert Tarjan
 |title=Fibonacci heaps and their uses in improved network optimization algorithms
 |url=http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Fibonacci-Heap-Tarjan.pdf
 |journal=[[Journal of the Association for Computing Machinery]]
 |volume=34 |issue=3 |date=July 1987 |pages=596&ndash;615
 |ref=harv |doi=10.1145/28869.28874
}}<!--See also 1994 paper by the same title at https://www.computer.org/csdl/proceedings/focs/1984/0591/00/0715934.pdf doi=10.1109/SFCS.1984.715934 --></ref>
! [[配对堆|配对]]<ref name="Iacono">{{citation
 | last = Iacono | first = John
 | contribution = Improved upper bounds for pairing heaps
 | url = http://john2.poly.edu/papers/swat00/paper.pdf
 | doi = 10.1007/3-540-44985-X_5
 | pages = 63–77
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proc. 7th Scandinavian Workshop on Algorithm Theory
 | isbn = 3-540-67690-2
 | volume = 1851
 | year = 2000
 | arxiv = 1110.4428}}</ref>
! [[Brodal队列|Brodal]]<ref>{{citation | last=Brodal | first=Gerth S. | contribution-url=http://www.cs.au.dk/~gerth/papers/soda96.pdf | contribution=Worst-Case Efficient Priority Queues | title=Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms |pages=52–58 | year=1996}}</ref>{{efn|name=brodal|Brodal和Okasaki后来描述了一个[[可持久化数据结构|可持久化]]的变种，拥有同样的运行上界，但不支持decrease-key。
带有''n''个元素的堆可以在''O''(''n'')时间内从下至上构建。<ref>{{cite book|title=Data Structures and Algorithms in Java|first1=Michael T.|last1=Goodrich|authorlink1=Michael T. Goodrich|first2=Roberto|last2=Tamassia|authorlink2=Roberto Tamassia|edition=3rd|year=2004|chapter=7.3.6. Bottom-Up Heap Construction|pages=338&ndash;341|isbn=0-471-46983-1}}</ref>}}

<!--
! [[Rank-pairing heap|Rank-pairing]]<ref>{{cite journal
 | last1 = Haeupler | first1 = Bernhard
 | last2 = Sen | first2 = Siddhartha
 | last3 = Tarjan | first3 = Robert E.
 | title = Rank-pairing heaps
 | journal = SIAM J. Computing
 | pages = 1463–1485
 | date = November 2011
 | doi = 10.1137/100785351
 | url = http://sidsen.org/papers/rp-heaps-journal.pdf}}</ref>
! [[Fibonacci heap|Strict Fibonacci]]<ref>{{Cite conference| doi = 10.1145/2213977.2214082| title = Strict Fibonacci heaps| conference = Proceedings of the 44th symposium on Theory of Computing - STOC '12| pages = 1177| year = 2012| last1 = Brodal | first1 = G. S. L. | last2 = Lagogiannis | first2 = G. | last3 = Tarjan | first3 = R. E. | isbn = 9781450312455| url = http://www.cs.au.dk/~gerth/papers/stoc12.pdf}}</ref>

-->
|-
| find-min
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|-
| delete-min
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized|均摊时间。}}
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
|style="background:#ffffdd"| ''O''(log ''n'')
|-
| insert
|style="background:#ffffdd"| ''O''(log ''n'')
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|-
| decrease-key
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ffdddd"| ''Θ''(''n'')
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
|style="background:#ffffdd"| ''o''(log ''n''){{efn|name=amortized}}{{efn|name=pairingdecreasekey|下界为<math>\Omega(\log\log n)</math>，<ref name="Fredman1999">{{cite journal |first=Michael Lawrence |last=Fredman |authorlink=Michael Fredman |title=On the Efficiency of Pairing Heaps and Related Data Structures |url=http://www.uqac.ca/azinflou/Fichiers840/EfficiencyPairingHeap.pdf |journal=[[Journal of the Association for Computing Machinery]] |volume=46 |issue=4 |pages=473&ndash;501 |date=July 1999 |doi=10.1145/320211.320214}}</ref>上界为<math>O(2^{2\sqrt{\log\log n}})</math>。<ref>{{cite conference |last=Pettie |first=Seth |title=Towards a Final Analysis of Pairing Heaps |conference=FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science |pages=174&ndash;183 |isbn=0-7695-2468-0 |doi=10.1109/SFCS.2005.75 |citeseerx=10.1.1.549.471 |year=2005 |url=http://web.eecs.umich.edu/~pettie/papers/focs05.pdf}}</ref>}}
|style="background:#ddffdd"| ''Θ''(1)
|-
| merge
|style="background:#ffdddd"| ''Θ''(''n'')
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=merge|''n''是较大堆的大小。}}
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|}
{{notelist}}