Difference between revisions of "Template:Heap Running Times"
Jump to navigation
Jump to search
(Fixed dead link, moved wrong Fredman paper to Fibonacci heap column where it belongs, insert right Fredman paper in pairing heap bounds footnote, other reference maintenance.) |
imported>Monkbot m (Task 18a (cosmetic) (manual): eval 10 templates: hyphenate params (11×);) |
||
(24 intermediate revisions by 20 users not shown) | |||
Line 1: | Line 1: | ||
− | + | <includeonly>Here are [[Computational complexity theory|time complexities]]<ref name="CLRS">{{Introduction to Algorithms|edition=1}}</ref> of various heap data structures. Function names assume a {{ #ifeq: {{{mode}}}| max | max | min }}-heap. For the meaning of "''O''(''f'')" and "''Θ''(''f'')" see [[Big O notation]]. | |
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
! Operation | ! Operation | ||
+ | ! find-{{ #ifeq: {{{mode}}}| max | max | min }} | ||
+ | ! delete-{{ #ifeq: {{{mode}}}| max | max | min }} | ||
+ | ! insert | ||
+ | ! {{ #ifeq: {{{mode}}}| max | increase | decrease }}-key | ||
+ | ! meld | ||
+ | |- | ||
! [[Binary heap|Binary]]<ref name="CLRS"/> | ! [[Binary heap|Binary]]<ref name="CLRS"/> | ||
− | ! [[Binomial heap|Binomial]]<ref name="CLRS"/> | + | |style="background:#ddffdd"| ''Θ''(1) |
+ | |style="background:#ffffdd"| ''Θ''(log ''n'') | ||
+ | |style="background:#ffffdd"| ''O''(log ''n'') | ||
+ | |style="background:#ffffdd"| ''O''(log ''n'') | ||
+ | |style="background:#ffdddd"| ''Θ''(''n'') | ||
+ | |- | ||
+ | ! [[Leftist tree|Leftist]] | ||
+ | |style="background:#ddffdd"| ''Θ''(1) | ||
+ | |style="background:#ffffdd"| ''Θ''(log ''n'') | ||
+ | |style="background:#ffffdd"| ''Θ''(log ''n'') | ||
+ | |style="background:#ffffdd"| ''O''(log ''n'') | ||
+ | |style="background:#ffffdd"| ''Θ''(log ''n'') | ||
+ | |- | ||
+ | ! [[Binomial heap|Binomial]]<ref name="CLRS"/><ref>{{Cite web|url=https://brilliant.org/wiki/binomial-heap/|title=Binomial Heap {{!}} Brilliant Math & Science Wiki|website=brilliant.org|language=en-us|access-date=2019-09-30}}</ref> | ||
+ | |style="background:#ddffdd"| ''Θ''(1) | ||
+ | |style="background:#ffffdd"| ''Θ''(log ''n'') | ||
+ | |style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized|Amortized time.}} | ||
+ | |style="background:#ffffdd"| ''Θ''(log ''n'') | ||
+ | |style="background:#ffffdd"| ''O''(log ''n''){{efn|name=meld|''n'' is the size of the larger heap.}} | ||
+ | |- | ||
! [[Fibonacci heap|Fibonacci]]<ref name="CLRS"/><ref name="Fredman And Tarjan">{{cite journal | ! [[Fibonacci heap|Fibonacci]]<ref name="CLRS"/><ref name="Fredman And Tarjan">{{cite journal | ||
− | |first1=Michael Lawrence |last1=Fredman | | + | |first1=Michael Lawrence |last1=Fredman |author-link1=Michael Fredman |
− | |first2=Robert E. |last2=Tarjan | | + | |first2=Robert E. |last2=Tarjan |author-link2=Robert Tarjan |
|title=Fibonacci heaps and their uses in improved network optimization algorithms | |title=Fibonacci heaps and their uses in improved network optimization algorithms | ||
|url=http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Fibonacci-Heap-Tarjan.pdf | |url=http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Fibonacci-Heap-Tarjan.pdf | ||
|journal=[[Journal of the Association for Computing Machinery]] | |journal=[[Journal of the Association for Computing Machinery]] | ||
− | |volume=34 |issue=3 |date=July 1987 |pages=596 | + | |volume=34 |issue=3 |date=July 1987 |pages=596-615 |
− | + | |doi=10.1145/28869.28874 |citeseerx=10.1.1.309.8927 | |
− | }}<!-- | + | }}<!-- An earlier version of this paper appeared in 1984 {{doi|10.1109/SFCS.1984.715934}}--></ref> |
+ | |style="background:#ddffdd"| ''Θ''(1) | ||
+ | |style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}} | ||
+ | |style="background:#ddffdd"| ''Θ''(1) | ||
+ | |style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}} | ||
+ | |style="background:#ddffdd"| ''Θ''(1) | ||
+ | |- | ||
! [[Pairing heap|Pairing]]<ref name="Iacono">{{citation | ! [[Pairing heap|Pairing]]<ref name="Iacono">{{citation | ||
− | | last = Iacono | first = John | + | | last = Iacono | first = John | author-link = John Iacono |
| contribution = Improved upper bounds for pairing heaps | | contribution = Improved upper bounds for pairing heaps | ||
+ | | url = http://john2.poly.edu/papers/swat00/paper.pdf | ||
| doi = 10.1007/3-540-44985-X_5 | | doi = 10.1007/3-540-44985-X_5 | ||
| pages = 63–77 | | pages = 63–77 | ||
Line 26: | Line 58: | ||
| volume = 1851 | | volume = 1851 | ||
| year = 2000 | | year = 2000 | ||
− | | arxiv = 1110.4428 | + | | arxiv = 1110.4428 |
− | + | | citeseerx = 10.1.1.748.7812}}</ref> | |
− | |||
− | |||
− | | | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
− | |style="background:#ffffdd"| '' | + | |style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}} |
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
+ | |style="background:#ffffdd"| ''o''(log ''n''){{efn|name=amortized}}{{efn|name=pairingdecreasekey|Lower bound of <math>\Omega(\log\log n),</math><ref name="Fredman1999">{{cite journal | ||
+ | |first=Michael Lawrence |last=Fredman |author-link=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–501 |date=July 1999 | ||
+ | |doi=10.1145/320211.320214 | ||
+ | }}</ref> upper bound of <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–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) | |style="background:#ddffdd"| ''Θ''(1) | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|- | |- | ||
− | | | + | ! [[Brodal queue|Brodal]]<ref>{{citation |
− | | | + | | last=Brodal | first=Gerth S. | author-link=Gerth Stølting Brodal |
− | | | + | | 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 and Okasaki later describe a [[Persistent_data_structure|persistent]] variant with the same bounds except for decrease-key, which is not supported. | ||
+ | Heaps with ''n'' elements can be constructed bottom-up in ''O''(''n'').<ref>{{cite book | ||
+ | |title=Data Structures and Algorithms in Java | ||
+ | |first1= Michael T. |last1=Goodrich |author-link1=Michael T. Goodrich | ||
+ | |first2=Roberto |last2=Tamassia |author-link2=Roberto Tamassia | ||
+ | |edition=3rd |year=2004 |chapter=7.3.6. Bottom-Up Heap Construction |pages=338-341 | ||
+ | |isbn=0-471-46983-1}}</ref>}} | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
+ | |style="background:#ffffdd"| ''O''(log ''n'') | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
+ | |- | ||
+ | ! [[Rank-pairing heap|Rank-pairing]]<ref>{{cite journal | ||
+ | | last1 = Haeupler | first1 = Bernhard | ||
+ | | last2 = Sen | first2 = Siddhartha | ||
+ | | last3 = Tarjan | first3 = Robert E. |author-link3 = Robert Tarjan | ||
+ | | title = Rank-pairing heaps | ||
+ | | journal = SIAM J. Computing | ||
+ | | volume = 40 | issue = 6 | pages = 1463–1485 | ||
+ | | date = November 2011 | ||
+ | | doi = 10.1137/100785351 | ||
+ | | url = http://sidsen.org/papers/rp-heaps-journal.pdf}}</ref> | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
− | + | |style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}} | |
− | |||
− | |style="background:#ffffdd"| '' | ||
− | |||
− | |||
− | |||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}} | |style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}} | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
|- | |- | ||
− | | | + | ! [[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–1184 | year = 2012 | ||
+ | | last1 = Brodal | first1 = Gerth Stølting | author-link1 = Gerth Stølting Brodal | ||
+ | | last2 = Lagogiannis | first2 = George | ||
+ | | last3 = Tarjan | first3 = Robert E.| author-link3 = Robert Tarjan | ||
+ | | isbn = 978-1-4503-1245-5 | ||
+ | | citeseerx = 10.1.1.233.1740 | ||
+ | | url = http://www.cs.au.dk/~gerth/papers/stoc12.pdf}}</ref> | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
+ | |style="background:#ffffdd"| ''O''(log ''n'') | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
+ | |- | ||
+ | ! [[2–3 heap]]<ref>{{citation | ||
+ | | last=Takaoka | first=Tadao | author-link=Tadao Takaoka | ||
+ | | url=https://ir.canterbury.ac.nz/bitstream/handle/10092/14769/2-3heaps.pdf | ||
+ | | title=Theory of 2–3 Heaps | ||
+ | | pages=12 | year=1999 | ||
+ | }}</ref> | ||
+ | |style="background:#ffffdd"| ''O''(log ''n'') | ||
+ | |style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}} | ||
+ | |style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}} | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
+ | |style="background:#ffffdd"| ''?'' | ||
|} | |} | ||
− | {{notelist}} | + | {{notelist}}</includeonly><noinclude>{{documentation}}</noinclude> |
Latest revision as of 20:21, 16 December 2020
Objective
{{Heap Running Times}} provides time complexity information for operations across different types of heaps.
Usage
{{Heap Running Times |mode = min}}
where
- mode
- optional parameter. If present and set to "max", present information for max heap; otherwise present for min heap
Examples
Here are time complexities[1] of various heap data structures. Function names assume a min-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.
Operation | find-min | delete-min | insert | decrease-key | meld |
---|---|---|---|---|---|
Binary[1] | Θ(1) | Θ(log n) | O(log n) | O(log n) | Θ(n) |
Leftist | Θ(1) | Θ(log n) | Θ(log n) | O(log n) | Θ(log n) |
Binomial[1][2] | Θ(1) | Θ(log n) | Θ(1)[lower-alpha 1] | Θ(log n) | O(log n)[lower-alpha 2] |
Fibonacci[1][3] | Θ(1) | O(log n)[lower-alpha 1] | Θ(1) | Θ(1)[lower-alpha 1] | Θ(1) |
Pairing[4] | Θ(1) | O(log n)[lower-alpha 1] | Θ(1) | o(log n)[lower-alpha 1][lower-alpha 3]).</math>[6]}} | Θ(1) |
Brodal[7][lower-alpha 4] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
Rank-pairing[9] | Θ(1) | O(log n)[lower-alpha 1] | Θ(1) | Θ(1)[lower-alpha 1] | Θ(1) |
Strict Fibonacci[10] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
2–3 heap[11] | O(log n) | O(log n)[lower-alpha 1] | O(log n)[lower-alpha 1] | Θ(1) | ? |
- ↑ Jump up to: 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 Amortized time.
- ↑ n is the size of the larger heap.
- ↑ Lower bound of <math>\Omega(\log\log n),</math>[5] upper bound of <math>O(2^{2\sqrt{\log\log n
- ↑ Brodal and Okasaki later describe a persistent variant with the same bounds except for decrease-key, which is not supported. Heaps with n elements can be constructed bottom-up in O(n).[8]
The above documentation is transcluded from Template:Heap Running Times/doc. (edit | history) Editors can experiment in this template's sandbox (create | mirror) and testcases (create) pages. Please add categories to the /doc subpage. Subpages of this template. |
- ↑ Jump up to: 1.0 1.1 1.2 1.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
- ↑ "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-09-30.
- ↑ Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.
- ↑ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2
- ↑ Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.
- ↑ Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.
- ↑ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
- ↑ Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.
- ↑ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
- ↑ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
- ↑ Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12