Difference between revisions of "Template:Heap Running Times"

From blackwiki
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:
In the following [[Computational complexity theory|time complexities]]<ref name="CLRS">{{Introduction to Algorithms|1}}</ref> ''O''(''f'') is an asymptotic upper bound and ''Θ''(''f'') is an asymptotically tight bound (see [[Big O notation]]). Function names assume a min-heap.
+
<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&nbsp;''n'')
 +
|style="background:#ffffdd"| ''O''(log&nbsp;''n'')
 +
|style="background:#ffffdd"| ''O''(log&nbsp;''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&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
  |first1=Michael Lawrence |last1=Fredman |authorlink1=Michael Fredman
+
  |first1=Michael Lawrence |last1=Fredman |author-link1=Michael Fredman
  |first2=Robert E. |last2=Tarjan |authorlink2=Robert 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&ndash;615
+
  |volume=34 |issue=3 |date=July 1987 |pages=596-615
  |ref=harv |doi=10.1145/28869.28874
+
  |doi=10.1145/28869.28874 |citeseerx=10.1.1.309.8927
}}<!--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>
+
}}<!-- 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&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 | 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}}</ref>
+
  | arxiv = 1110.4428
! [[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.
+
  | citeseerx = 10.1.1.748.7812}}</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&ndash;341|isbn=0-471-46983-1}}</ref>}}
 
! [[Rank-pairing heap|Rank-pairing]]<ref>{{cite journal
 
  | last1 = Haeupler | first1 = Bernhard
 
| last2 = Sen | first2 = Siddhartha
 
| last3 = Tarjan | first3 = Robert E.
 
| title = Rank-pairing heaps
 
| journal = SIAM J. Computing
 
| pages = 1463–1485
 
| year = 2009
 
| url = http://www.cs.princeton.edu/~sssix/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>
 
|-
 
| find-min
 
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ffffdd"| ''Θ''(log ''n'')
+
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
 
|style="background:#ddffdd"| ''Θ''(1)
 
|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 |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&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)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|-
 
| delete-min
 
|style="background:#ffffdd"| ''Θ''(log ''n'')
 
|style="background:#ffffdd"| ''Θ''(log ''n'')
 
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized|Amortized time.}}
 
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
 
|style="background:#ffffdd"| ''O''(log ''n'')
 
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
 
|style="background:#ffffdd"| ''O''(log ''n'')
 
 
|-
 
|-
| insert
+
! [[Brodal queue|Brodal]]<ref>{{citation
|style="background:#ffffdd"| ''O''(log ''n'')
+
| last=Brodal | first=Gerth S. | author-link=Gerth Stølting Brodal
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
+
| 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&nbsp;''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}}
| decrease-key
 
|style="background:#ffffdd"| ''Θ''(log ''n'')
 
|style="background:#ffffdd"| ''Θ''(log ''n'')
 
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
 
|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&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){{efn|name=amortized}}
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|-
 
|-
| merge
+
! [[Fibonacci heap|Strict Fibonacci]]<ref>{{Cite conference
|style="background:#ffdddd"| ''Θ''(''n'')
+
| doi = 10.1145/2213977.2214082
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=merge|''n'' is the size of the larger heap.}}
+
| 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

Template documentation[view] [edit] [history] [purge]

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. Jump up to: 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>[5] 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).[8]
  1. 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.
  2. "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-09-30.
  3. 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.
  4. 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
  5. 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.
  6. 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.
  7. Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
  8. 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.
  9. Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
  10. 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.
  11. Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12