Difference between revisions of "Template:Heap Running Times"
Jump to navigation
Jump to search
imported>Arthur MILCHIOR (Undid revision 740157890 by 2001:388:E000:BA00:4D0B:E82B:C093:F632 (talk) O and Theta have different meaning, as explained above the tabl) |
imported>Monkbot m (Task 18a (cosmetic) (manual): eval 10 templates: hyphenate params (11×);) |
||
(25 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) |
− | ! [[Fibonacci heap|Fibonacci]]<ref name="CLRS"/> | + | |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 | ||
+ | |first1=Michael Lawrence |last1=Fredman |author-link1=Michael Fredman | ||
+ | |first2=Robert E. |last2=Tarjan |author-link2=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-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 15: | Line 55: | ||
| series = Lecture Notes in Computer Science | | series = Lecture Notes in Computer Science | ||
| title = Proc. 7th Scandinavian Workshop on Algorithm Theory | | title = Proc. 7th Scandinavian Workshop on Algorithm Theory | ||
+ | | isbn = 3-540-67690-2 | ||
| volume = 1851 | | volume = 1851 | ||
− | | year = 2000 | + | | year = 2000 |
− | + | | arxiv = 1110.4428 | |
− | + | | citeseerx = 10.1.1.748.7812}}</ref> | |
− | |||
− | |||
− | |||
− | | | ||
− | | | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
+ | |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) | ? |
- ↑ 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. |
- ↑ 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