Indicwiki: 1 revision imported from :alpha:Template:Heap_Running_Times

2023-07-21T07:08:45Z

1 revision imported from alpha:Template:Heap_Running_Times

← Older revision	Revision as of 12:38, 21 July 2023
(No difference)

alpha>Indicwiki: Created page with "Here are time complexities{{Introduction to Algorithms|edition=1}} of various heap data structures. Fun..."

2023-07-07T04:48:06Z

Created page with "<includeonly>Here are time complexities<ref name="CLRS">{{Introduction to Algorithms|edition=1}}</ref> of various heap data structures. Fun..."

New page

<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"
|-
! 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"/>
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ffffdd"| ''O''(log ''n'')
|style="background:#ffffdd"| ''O''(log ''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 ''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
|first1=Michael Lawrence |last1=Fredman |author-link1=Michael Fredman
|first2=Robert E. |last2=Tarjan |author-link2=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
|doi=10.1145/28869.28874 |citeseerx=10.1.1.309.8927
}}</ref>
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ffffdd"| ''O''(log ''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
| last = Iacono | first = John | author-link = John Iacono
| contribution = Improved upper bounds for pairing heaps
| url = http://john2.poly.edu/papers/swat00/paper.pdf
| doi = 10.1007/3-540-44985-X_5
| pages = 63–77
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = Proc. 7th Scandinavian Workshop on Algorithm Theory
| isbn = 3-540-67690-2
| volume = 1851
| year = 2000
| arxiv = 1110.4428
| citeseerx = 10.1.1.748.7812}}</ref>
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
|style="background:#ddffdd"| ''Θ''(1)
|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 |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–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)
|-
! [[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 ''n'')
|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:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
|style="background:#ddffdd"| ''Θ''(1)
|-
! [[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–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:#ffffdd"| ''O''(log ''n'')
|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:#ffffdd"| ''?''
|}
{{notelist}}</includeonly><noinclude>{{documentation}}</noinclude>

Template:Heap Running Times - Revision history

Indicwiki: 1 revision imported from :alpha:Template:Heap_Running_Times

alpha>Indicwiki: Created page with "Here are time complexities{{Introduction to Algorithms|edition=1}} of various heap data structures. Fun..."