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) |
(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.) |
||
Line 6: | Line 6: | ||
! [[Binary heap|Binary]]<ref name="CLRS"/> | ! [[Binary heap|Binary]]<ref name="CLRS"/> | ||
! [[Binomial heap|Binomial]]<ref name="CLRS"/> | ! [[Binomial heap|Binomial]]<ref name="CLRS"/> | ||
− | ! [[Fibonacci heap|Fibonacci]]<ref name="CLRS"/> | + | ! [[Fibonacci heap|Fibonacci]]<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–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> | ||
! [[Pairing heap|Pairing]]<ref name="Iacono">{{citation | ! [[Pairing heap|Pairing]]<ref name="Iacono">{{citation | ||
| last = Iacono | first = John | | last = Iacono | first = John | ||
Line 15: | Line 23: | ||
| 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}}</ref> | + | | year = 2000 |
− | ! [[Brodal queue|Brodal]]<ref>{{citation | last=Brodal | first=Gerth S. | 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. | + | | arxiv = 1110.4428}}</ref> |
− | 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|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–341}}</ref>}} | + | ! [[Brodal queue|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 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|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–341|isbn=0-471-46983-1}}</ref>}} | ||
! [[Rank-pairing heap|Rank-pairing]]<ref>{{cite journal | ! [[Rank-pairing heap|Rank-pairing]]<ref>{{cite journal | ||
| last1 = Haeupler | first1 = Bernhard | | last1 = Haeupler | first1 = Bernhard | ||
Line 61: | Line 71: | ||
|style="background:#ffffdd"| ''Θ''(log ''n'') | |style="background:#ffffdd"| ''Θ''(log ''n'') | ||
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}} | |style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}} | ||
− | |style="background:#ffffdd"| ''o''(log ''n''){{efn|name=amortized}}{{efn|name=pairingdecreasekey| | + | |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 |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–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) | ||
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}} | |style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}} |
Revision as of 09:01, 29 December 2016
In the following time complexities[1] O(f) is an asymptotic upper bound and Θ(f) is an asymptotically tight bound (see Big O notation). Function names assume a min-heap.
Operation | Binary[1] | Binomial[1] | Fibonacci[1][2] | Pairing[3] | Brodal[4][lower-alpha 1] | Rank-pairing[6] | Strict Fibonacci[7] |
---|---|---|---|---|---|---|---|
find-min | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
delete-min | Θ(log n) | Θ(log n) | O(log n)[lower-alpha 2] | O(log n)[lower-alpha 2] | O(log n) | O(log n)[lower-alpha 2] | O(log n) |
insert | O(log n) | Θ(1)[lower-alpha 2] | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
decrease-key | Θ(log n) | Θ(log n) | Θ(1)[lower-alpha 2] | o(log n)[lower-alpha 2][lower-alpha 3]).</math>[9]}} | Θ(1) | Θ(1)[lower-alpha 2] | Θ(1) |
merge | Θ(n) | O(log n)[lower-alpha 4] | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
- ↑ 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).[5]
- ↑ Jump up to: 2.0 2.1 2.2 2.3 2.4 2.5 2.6 Amortized time.
- ↑ Lower bound of <math>\Omega(\log\log n),</math>[8] upper bound of <math>O(2^{2\sqrt{\log\log n
- ↑ n is the size of the larger heap.
- ↑ 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.
- ↑ 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. doi:10.1145/28869.28874.CS1 maint: ref=harv (link)
- ↑ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2
- ↑ 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. (2009). "Rank-pairing heaps" (PDF). SIAM J. Computing: 1463–1485.
- ↑ Brodal, G. S. L.; Lagogiannis, G.; Tarjan, R. E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. p. 1177. doi:10.1145/2213977.2214082. ISBN 9781450312455.
- ↑ 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.