Difference between revisions of "Template:Heap Running Times"

From blackwiki
Jump to navigation Jump to search
(Add URL to Iacono paper)
imported>Monkbot
m (Task 18a (cosmetic) (manual): eval 10 templates: hyphenate params (11×);)
 
(22 intermediate revisions by 18 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
 
  | url = http://john2.poly.edu/papers/swat00/paper.pdf
Line 27: 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>}}
+
|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 |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)
 +
|-
 +
! [[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:#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
 
  | last2 = Sen | first2 = Siddhartha
 
  | last2 = Sen | first2 = Siddhartha
  | last3 = Tarjan | first3 = Robert E.
+
  | last3 = Tarjan | first3 = Robert E. |author-link3 = Robert Tarjan
 
  | title = Rank-pairing heaps
 
  | title = Rank-pairing heaps
 
  | journal = SIAM J. Computing
 
  | journal = SIAM J. Computing
  | pages = 1463–1485
+
  | volume = 40 | issue = 6 | pages = 1463–1485
 
  | date = November 2011
 
  | date = November 2011
 
  | 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>
 
|-
 
| find-min
 
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ffffdd"| ''Θ''(log ''n'')
 
|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''){{efn|name=amortized}}
|style="background:#ffffdd"| ''O''(log ''n'')
 
|-
 
| insert
 
|style="background:#ffffdd"| ''O''(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)
 
|-
 
| 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