Difference between revisions of "Template:Heap Running Times"

From blackwiki
Jump to navigation Jump to search
imported>Alexey Muranov
(Rewrite the introduction paragraph. (In particular, trying to define or summarize here the meaning of "big O" is useless: ether the reader already knows it, or it is not going to help.))
(Per Heap and standard usage in the literature, call the destructive combining operation "meld" rather than "merge")
Line 8: Line 8:
 
! insert
 
! insert
 
! decrease-key
 
! decrease-key
! merge
+
! meld
 
|-
 
|-
 
! [[Binary heap|Binary]]<ref name="CLRS"/>
 
! [[Binary heap|Binary]]<ref name="CLRS"/>
Line 29: Line 29:
 
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized|Amortized time.}}
 
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized|Amortized time.}}
 
|style="background:#ffffdd"| ''Θ''(log ''n'')
 
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ffffdd"| ''O''(log&nbsp;''n''){{efn|name=merge|''n'' is the size of the larger heap.}}
+
|style="background:#ffffdd"| ''O''(log&nbsp;''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

Revision as of 05:30, 2 July 2019

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] Θ(log n) Θ(log n) Θ(1)[lower-alpha 1] Θ(log n) O(log n)[lower-alpha 2]
Fibonacci[1][2] Θ(1) O(log n)[lower-alpha 1] Θ(1) Θ(1)[lower-alpha 1] Θ(1)
Pairing[3] Θ(1) O(log n)[lower-alpha 1] Θ(1) o(log n)[lower-alpha 1][lower-alpha 3]).</math>[5]}} Θ(1)
Brodal[6][lower-alpha 4] Θ(1) O(log n) Θ(1) Θ(1) Θ(1)
Rank-pairing[8] Θ(1) O(log n)[lower-alpha 1] Θ(1) Θ(1)[lower-alpha 1] Θ(1)
Strict Fibonacci[9] Θ(1) O(log n) Θ(1) Θ(1) Θ(1)
2-3 heap ? O(log n)[lower-alpha 1] O(log n)[lower-alpha 1] Θ(1) ?
  1. 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 Amortized time.
  2. n is the size of the larger heap.
  3. Lower bound of <math>\Omega(\log\log n),</math>[4] upper bound of <math>O(2^{2\sqrt{\log\log n
  4. 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).[7]
  1. 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.
  2. 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.CS1 maint: ref=harv (link)
  3. 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
  4. 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.
  5. 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.
  6. Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
  7. 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.
  8. Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
  9. 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.