Difference between revisions of "Template:Heap Running Times"

From blackwiki
Jump to navigation Jump to search
(Stop stupid line breaks between "log" and "n". Better having to horizontally scroll than read that mess.)
(Transpose table to avoid excessive width. Now 6 columns, 10 rows, and additional heap types add rows rather than width.)
Line 4: Line 4:
 
|-
 
|-
 
! Operation
 
! Operation
 +
! find-min
 +
! delete-min
 +
! insert
 +
! decrease-key
 +
! merge
 +
|-
 
! [[Binary heap|Binary]]<ref name="CLRS"/>
 
! [[Binary heap|Binary]]<ref name="CLRS"/>
 +
|style="background:#ddffdd"| ''Θ''(1)
 +
|style="background:#ffffdd"| ''Θ''(log&nbsp;''n'')
 +
|style="background:#ffffdd"| ''O''(log&nbsp;'n'')
 +
|style="background:#ffffdd"| ''O''(log&nbsp;''n'')
 +
|style="background:#ffdddd"| ''Θ''(''n'')
 +
|-
 
! [[Leftist tree|Leftist]]
 
! [[Leftist tree|Leftist]]
 +
|style="background:#ddffdd"| ''Θ''(1)
 +
|style="background:#ffffdd"| ''Θ''(log ''n'')
 +
|style="background:#ffffdd"| ''Θ''(log ''n'')
 +
|style="background:#ffdddd"| ''Θ''(''n'')
 +
|style="background:#ffffdd"| ''Θ''(log ''n'')
 +
|-
 
! [[Binomial heap|Binomial]]<ref name="CLRS"/>
 
! [[Binomial heap|Binomial]]<ref name="CLRS"/>
 +
|style="background:#ffffdd"| ''Θ''(log ''n'')
 +
|style="background:#ffffdd"| ''Θ''(log ''n'')
 +
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized|Amortized time.}}
 +
|style="background:#ffffdd"| ''Θ''(log ''n'')
 +
|style="background:#ffffdd"| ''O''(log&nbsp;''n''){{efn|name=merge|''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 |authorlink1=Michael Fredman
 
  |first1=Michael Lawrence |last1=Fredman |authorlink1=Michael Fredman
Line 16: Line 40:
 
  |ref=harv |doi=10.1145/28869.28874
 
  |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>
 
}}<!--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>
 +
|style="background:#ddffdd"| ''Θ''(1)
 +
|style="background:#ffffdd"| ''O''(log&nbsp;''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
Line 29: Line 59:
 
  | year = 2000
 
  | year = 2000
 
  | arxiv = 1110.4428}}</ref>
 
  | arxiv = 1110.4428}}</ref>
 +
|style="background:#ddffdd"| ''Θ''(1)
 +
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
 +
|style="background:#ddffdd"| ''Θ''(1)
 +
|style="background:#ffffdd"| ''o''(log&nbsp;''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&ndash;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&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)
 +
|-
 
! [[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.
 
! [[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>}}
 
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>}}
 +
|style="background:#ddffdd"| ''Θ''(1)
 +
|style="background:#ffffdd"| ''O''(log&nbsp;''n'')
 +
|style="background:#ddffdd"| ''Θ''(1)
 +
|style="background:#ddffdd"| ''Θ''(1)
 +
|style="background:#ddffdd"| ''Θ''(1)
 +
|-
 
! [[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 41: Line 83:
 
  | doi = 10.1137/100785351
 
  | doi = 10.1137/100785351
 
  | url = http://sidsen.org/papers/rp-heaps-journal.pdf}}</ref>
 
  | 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>
 
! [[2-3 heap]]
 
|-
 
| find-min
 
 
|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"| ''Θ''(log ''n'')
+
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ffffdd"| ''?''
 
 
|-
 
|-
| delete-min
+
! [[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>
|style="background:#ffffdd"| ''Θ''(log&nbsp;''n'')
 
|style="background:#ffffdd"| ''Θ''(log&nbsp;''n'')
 
|style="background:#ffffdd"| ''Θ''(log&nbsp;''n'')
 
|style="background:#ffffdd"| ''O''(log&nbsp;''n''){{efn|name=amortized|Amortized time.}}
 
|style="background:#ffffdd"| ''O''(log&nbsp;''n''){{efn|name=amortized}}
 
|style="background:#ffffdd"| ''O''(log&nbsp;''n'')
 
|style="background:#ffffdd"| ''O''(log&nbsp;''n''){{efn|name=amortized}}
 
|style="background:#ffffdd"| ''O''(log&nbsp;''n'')
 
|style="background:#ffffdd"| ''O''(log&nbsp;''n''){{efn|name=amortized}}
 
|-
 
| 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)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
 
|-
 
| decrease-key
 
 
|style="background:#ffffdd"| ''O''(log ''n'')
 
|style="background:#ffffdd"| ''O''(log ''n'')
|style="background:#ffdddd"| ''Θ''(''n'')
 
|style="background:#ffffdd"| ''Θ''(log ''n'')
 
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
 
|style="background:#ffffdd"| ''o''(log&nbsp;''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&ndash;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&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)
 
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
 
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|-
 
|-
| merge
+
! [[2-3 heap]]
|style="background:#ffdddd"| ''Θ''(''n'')
+
|style="background:#ffffdd"| ''?''
|style="background:#ffffdd"| ''Θ''(log ''n'')
+
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=merge|''n'' is the size of the larger heap.}}
+
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ffffdd"| ''?''
 
|style="background:#ffffdd"| ''?''
 
|}
 
|}
 
{{notelist}}
 
{{notelist}}

Revision as of 04:38, 3 March 2019

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 find-min delete-min insert decrease-key merge
Binary[1] Θ(1) Θ(log n) O(log 'n) O(log n) Θ(n)
Leftist Θ(1) Θ(log n) Θ(log n) Θ(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. 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, 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: 1463–1485. doi:10.1137/100785351.
  9. 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.