blackwiki - User contributions [en]

Template:Infobox CPU architecture

2019-03-29T11:02:38Z

209.209.238.189: Fixed capitalization error in template parameter name

{{Infobox
| title = {{{title|{{{name|<includeonly>{{PAGENAMEBASE}}</includeonly>}}}}}}
| image = {{#invoke:InfoboxImage|InfoboxImage|image={{{image|}}}|size={{{image_size|}}}|alt={{{alt|}}}}}
| caption = {{{caption|}}}

| label1 = Designer
| data1 = {{{designer|}}}
| label2 = Bits
| data2 = {{{bits|}}}
| label3 = Introduced
| data3 = {{{introduced|}}}
| label4 = Version
| data4 = {{{version|}}}
| label5 = [[Computer architecture|Design]]
| data5 = {{{design|}}}
| label6 = Type
| data6 = {{{type|}}}
| label7 = [[Instruction set|Encoding]]
| data7 = {{{encoding|}}}
| label8 = [[Branch (computer science)|Branching]]
| data8 = {{{branching|}}}
| label9 = [[Endianness]]
| data9 = {{{endianness|}}}
| label10 = Page size
| data10 = {{{page size|}}}
| label11 = Extensions
| data11 = {{{extensions|}}}
| label12 = Open
| data12 = {{{open|}}}
| label13 = Predecessor
| data13 = {{{predecessor|}}}
| label14 = Successor
| data14 = {{{successor|}}}

| header15 = {{#if:{{{gpr|}}}{{{fpr|}}}{{{registers|}}}|[[Processor register|Registers]]}}

| data16 = {{{registers|}}}
| label17 = [[General purpose register|General purpose]]
| data17 = {{{gpr|}}}
| label18 = [[Floating point]]
| data18 = {{{fpr|}}}

}}<noinclude>{{documentation}}</noinclude>

Template:Infobox CPU architecture/doc

2019-03-29T10:56:21Z

209.209.238.189: Added docs for "Predecessor" and "Successor" links.

{{Documentation subpage}}

This template is for CPU [[instruction set architecture]]s.

=== Usage ===
<pre>
{{Infobox CPU architecture
| name =
| designer =
| bits =
| introduced =
| version =
| design =
| type =
| encoding =
| branching =
| endianness =
| page size =
| extensions =
| open =
| predecessor =
| successor =
| registers =
| gpr =
| fpr =
}}
</pre>

=== Description ===
<pre>
{{Infobox CPU architecture
| name = Name of architecture, e.g. x86, SPARC, PowerPC, MIPS, ARM
| designer = Designer of the architecture
| bits = Width of accumulator/general registers/stack top, e.g. 32-bit, 64-bit
| introduced = Year introduced
| version = Version/revision of architecture/ISA
| design = Design strategy, e.g. RISC, CISC
| type = Type of architecture, e.g. Register-Register, Register-Memory, Memory-Memory
| encoding = Instruction set encoding, e.g. Fixed or Variable
| branching = Branching evaluation, e.g. Condition register, Condition code, Compare and branch
| endianness = Byte ordering, i.e. Little, Big, Bi
| page size = Primary size of page, i.e. 4 KiB, 2 MiB, 1 GiB; does not include "huge pages" and other extensions
| extensions = ISA extensions, i.e. MMX, SSE, AltiVec, etc
| open = Is the architecture open or not? (as in free or proprietary)
| predecessor = Earlier architecture(s) this one is based on, if it has a separate page
| successor = Later architecture(s) based primarily on this one, if it has a separate page
| open = Is the architecture open or not? (as in free or proprietary)
| registers = Number and size of processor registers
| gpr = Number of general-purpose registers (and size, if not indicated by bits=)
| fpr = Number of floating-point registers (and size, if not indicated by bits=)
}}
</pre>
All fields are optional.

=== Example ===
{{Infobox CPU architecture
| name = SPARC
| designer = [[Sun Microsystems]]
| bits = 64-bit (32 → 64)
| introduced = 1985
| version = V9 (1993)
| design = RISC
| type = Register-Register
| encoding = Fixed
| branching = Condition code
| endianness = Bi (Big → Bi)
| page size = 8 KiB
| extensions = [[Visual Instruction Set|VIS]] 1.0, 2.0, 3.0
| open = Yes
| gpr = 31 (G0 = 0; non-global registers use [[register window]]s)
| fpr = 32
}}
<pre>
{{Infobox CPU architecture
| name = SPARC
| designer = [[Sun Microsystems]]
| bits = 64-bit (32 → 64)
| introduced = 1985
| version = V9 (1993)
| design = RISC
| type = Register-Register
| encoding = Fixed
| branching = Condition code
| endianness = Bi (Big → Bi)
| page size = 8 KiB
| extensions = [[Visual Instruction Set|VIS]] 1.0, 2.0, 3.0
| open = Yes
| gpr = 31 (G0 = 0; non-global registers use [[register window]]s)
| fpr = 32
}}
</pre>

=== Parameters ===
All parameters are optional.
; name: Name of architecture, e.g. x86, SPARC, PowerPC, MIPS, ARM
; designer: Designer of the architecture
; bits: Width of accumulator/general registers/stack top, e.g. 32-bit, 64-bit
; introduced: Year introduced
; version: Version/revision of architecture/ISA
; design: Design strategy, e.g. RISC, CISC
; type: Type of architecture, e.g. Register-Register, Register-Memory, Memory-Memory
; encoding: Instruction set encoding, e.g. Fixed or Variable
; branching: Branching evaluation, e.g. Condition register, Condition code, Compare and branch
; endianness: Byte ordering, e.g. Little, Big, Bi
; page size: Primary size of page, e.g. 4 KiB, 2 MiB, 1 GiB; does not include "huge pages" and other extensions
; extensions: ISA extensions, e.g. MMX, SSE, AltiVec
; open: Is the architecture open or not? (as in free or proprietary)
; predecessor: Earlier architecture(s) this one is based on, if it has a separate page
; successor: Later architecture(s) based primarily on this one, if it has a separate page

; registers: Number and size of processor registers
; gpr: Number of general-purpose registers (and size, if not indicated by bits=)
; fpr: Number of floating-point registers (and size, if not indicated by bits=)

=== See also ===
* {{Lts|Infobox CPU}} for [[central processing unit]]s
* {{Lts|Infobox computer hardware bus}} for [[Bus (computing)|computer bus]]es

<includeonly>

[[Category:Computer hardware infobox templates|CPU architecture]]
</includeonly>

Template:Infobox CPU architecture

2019-03-29T10:52:40Z

209.209.238.189: Added "Predecessor" and "Successor" links, for families with multiple pages

{{Infobox
| title = {{{title|{{{name|<includeonly>{{PAGENAMEBASE}}</includeonly>}}}}}}
| image = {{#invoke:InfoboxImage|InfoboxImage|image={{{image|}}}|size={{{image_size|}}}|alt={{{alt|}}}}}
| caption = {{{caption|}}}

| label1 = Designer
| data1 = {{{designer|}}}
| label2 = Bits
| data2 = {{{bits|}}}
| label3 = Introduced
| data3 = {{{introduced|}}}
| label4 = Version
| data4 = {{{version|}}}
| label5 = [[Computer architecture|Design]]
| data5 = {{{design|}}}
| label6 = Type
| data6 = {{{type|}}}
| label7 = [[Instruction set|Encoding]]
| data7 = {{{encoding|}}}
| label8 = [[Branch (computer science)|Branching]]
| data8 = {{{branching|}}}
| label9 = [[Endianness]]
| data9 = {{{endianness|}}}
| label10 = Page size
| data10 = {{{page size|}}}
| label11 = Extensions
| data11 = {{{extensions|}}}
| label12 = Open
| data12 = {{{open|}}}
| label13 = Predecessor
| data13 = {{{predecessor|}}}
| label14 = Successor
| data14 = {{{Successor|}}}

| header15 = {{#if:{{{gpr|}}}{{{fpr|}}}{{{registers|}}}|[[Processor register|Registers]]}}

| data16 = {{{registers|}}}
| label17 = [[General purpose register|General purpose]]
| data17 = {{{gpr|}}}
| label18 = [[Floating point]]
| data18 = {{{fpr|}}}

}}<noinclude>{{documentation}}</noinclude>

Template:Heap Running Times

2019-03-10T03:38:18Z

209.209.238.189: Improve existing refs with citeseerx links, authorlinks, etc.

In the following [[Computational complexity theory|time complexities]]<ref name="CLRS">{{Introduction to Algorithms|edition=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.

{| class="wikitable"
|-
! Operation
! find-min
! delete-min
! insert
! decrease-key
! merge
|-
! [[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:#ffdddd"| ''Θ''(''n'')
|style="background:#ffffdd"| ''Θ''(log ''n'')
|-
! [[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 ''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
|first1=Michael Lawrence |last1=Fredman |authorlink1=Michael Fredman
|first2=Robert E. |last2=Tarjan |authorlink2=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
|ref=harv |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 | authorlink = 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 |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–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. | authorlink=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 |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 ''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. |authorlink3 = 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 | authorlink1 = Gerth Stølting Brodal
| last2 = Lagogiannis | first2 = George
| last3 = Tarjan | first3 = Robert E.| authorlink3 = 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]]
|style="background:#ffffdd"| ''?''
|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}}

Template:Heap Running Times

2019-03-03T04:38:04Z

209.209.238.189: Transpose table to avoid excessive width. Now 6 columns, 10 rows, and additional heap types add rows rather than width.

In the following [[Computational complexity theory|time complexities]]<ref name="CLRS">{{Introduction to Algorithms|edition=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.

{| class="wikitable"
|-
! Operation
! find-min
! delete-min
! insert
! decrease-key
! merge
|-
! [[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:#ffdddd"| ''Θ''(''n'')
|style="background:#ffffdd"| ''Θ''(log ''n'')
|-
! [[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 ''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
|first1=Michael Lawrence |last1=Fredman |authorlink1=Michael Fredman
|first2=Robert E. |last2=Tarjan |authorlink2=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
|ref=harv |doi=10.1145/28869.28874
}}</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
| 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}}</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 |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–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. | 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>}}
|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.
| title = Rank-pairing heaps
| journal = SIAM J. Computing
| 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| 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:#ddffdd"| ''Θ''(1)
|style="background:#ffffdd"| ''O''(log ''n'')
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|-
! [[2-3 heap]]
|style="background:#ffffdd"| ''?''
|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}}

Template:Heap Running Times

2019-03-03T04:24:09Z

209.209.238.189: Stop stupid line breaks between "log" and "n". Better having to horizontally scroll than read that mess.

In the following [[Computational complexity theory|time complexities]]<ref name="CLRS">{{Introduction to Algorithms|edition=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.

{| class="wikitable"
|-
! Operation
! [[Binary heap|Binary]]<ref name="CLRS"/>
! [[Leftist tree|Leftist]]
! [[Binomial heap|Binomial]]<ref name="CLRS"/>
! [[Fibonacci heap|Fibonacci]]<ref name="CLRS"/><ref name="Fredman And Tarjan">{{cite journal
|first1=Michael Lawrence |last1=Fredman |authorlink1=Michael Fredman
|first2=Robert E. |last2=Tarjan |authorlink2=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
|ref=harv |doi=10.1145/28869.28874
}}</ref>
! [[Pairing heap|Pairing]]<ref name="Iacono">{{citation
| last = Iacono | first = John
| 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}}</ref>
! [[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>}}
! [[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
| date = November 2011
| doi = 10.1137/100785351
| 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"| ''Θ''(log ''n'')
|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
|style="background:#ffffdd"| ''Θ''(log ''n'')
|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'')
|style="background:#ffffdd"| ''O''(log ''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:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
|-
| decrease-key
|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 ''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–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)
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|-
| merge
|style="background:#ffdddd"| ''Θ''(''n'')
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=merge|''n'' is the size of the larger heap.}}
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ddffdd"| ''Θ''(1)
|style="background:#ffffdd"| ''?''
|}
{{notelist}}

Template:Bells

2018-09-16T23:23:43Z

209.209.238.189: Grassmayr Foundry as redlink. Est. 1599 and still casting about 300/year, definitely notable.

{{Navbox
| name = Bells
| state = {{{state<includeonly>|autocollapse</includeonly>}}}
| title = [[Bell]]s
| listclass = hlist
| image = [[File:Church bell cutaway.png|150px|alt=]]

| group1 = Background and <br/>terminology
| list1 =
* [[Bell]]
* [[Bell-cot]]
* [[Bellfounding]]
* [[Bell-gable]]
* [[Bell tower|Bell tower / Campanile]]
* [[Bell-ringer]]
* [[Belfry (architecture)|Belfry]]
* [[Bourdon (bell)|Bourdon]]
* [[Campanology]]
* [[Church bell]]
* [[Full circle ringing]]
* [[Peal]]
* [[Ring of bells]]
* [[Strike tone]]
* [[Striking clock]]
* [[Zvonnitsa]]

| group2 = Types
| list2 =
* [[Agogô]]
* [[Altar bell]]
* [[Babendil]]
* [[Bianzhong]]
* [[Bicycle bell]]
* [[Bonshō]]
* [[Call bell]]
* [[Carillon]]
* [[Chime (bell instrument)|Chime]]
* [[Cowbell (instrument)|Cowbell]]
* [[Crotal bell]]
* [[Dead bell]]
* [[Doorbell]]
* [[Dōtaku]]
* [[Ghanta]]
* [[Glockenspiel]]
* [[Handbell]]
* [[Jingle bell]]
* [[Kane (instrument)|Kane]]
* [[Ship's bell]]
* [[Standing bell]]
* [[Suzu]]
* [[Tintinnabulum]]
* [[Tubular bells]]

| group3 = Ringing styles
| list3 =
* [[Bell pattern]]
* [[Blagovest]]
* [[Bolognese bell ringing art]]
* [[Change ringing]]
* [[Canpanò]]
* [[Grandsire]]
* [[Method ringing]]
* [[Peal]]
* [[Russian Orthodox bell ringing]]
* [[Veronese bellringing art]]

| group4 = Notable bells
| list4 =
* [[List of heaviest bells]]
* [[Balangiga bells]]
* [[Bell of Good Luck]]
* [[Big Ben]]
* [[Freedom Bell]]
* [[Great Bell of Dhammazedi]]
* [[Tom Tower|Great Tom]]
* [[Ivan the Great Bell Tower]]
* [[Japanese Peace Bell]]
* [[Justice Bell (Valley Forge)|Justice Bell]]
* [[Liberty Bell]]
* [[Maria Gloriosa]]
* [[Mingun Bell]]
* [[Olympic Bell]]
* [[Sigismund Bell]]
* [[St. Petersglocke]]
* [[Swan Bells]]
* [[Tsar Bell]]
* [[World Peace Bell Association|World Peace Bells]]
* [[Big Bell Temple|Yongle Big Bell]]

| group5 = Bell founders <br/>and foundries
| list5 =
* [[Andrey Chokhov]]
* [[Bilbie family]]
* [[Franciscus Illenfeld]]
* [[Geert van Wou]]
* [[Gillett & Johnston]]
* [[Grassmayr Foundry]]
* [[Hatch bell foundry]]
* [[John Taylor & Co]]
* [[Juutila Foundry]]
* [[Kashpir Ganusov]]
* [[McShane Bell Foundry]]
* [[Meneely Bell Foundry]]
* [[Pieter and François Hemony]]
* [[Petit & Fritsen]]
* [[Royal Eijsbouts bell foundry]]
* [[Rudhall of Gloucester]]
* [[Whitechapel Bell Foundry]]

| group6 = Related
| list6 =
* ''[[The Ringing World]]''
* ''[[Dove's Guide for Church Bell Ringers]]''
* [[Glockenmuseum Stiftskirche Herrenberg]]
* [[Liberty Bell Museum]]
* [[List of bell ringing organisations|Ringing Organisations]]
* [[American Legion Freedom Bell|''Freedom Bell, American Legion'']]

}}<includeonly>
</includeonly><noinclude>
{{documentation|content=
{{collapsible option}}

==See also==
*{{tl|Vessel percussion idiophones}}

[[Category:Musical instrument templates]]
}}
</noinclude>