Data Structures and Algorithms - Versionsgeschichte

Hannes am 24. November 2007 um 13:18 Uhr

2007-11-24T13:18:08Z

Hannes am 24. November 2007 um 13:16 Uhr

2007-11-24T13:16:16Z

Hannes: /* Heaps */

2007-11-24T13:14:28Z

‎Heaps

Hannes: /* Fibonacci heap */

2007-11-24T13:13:20Z

‎Fibonacci heap

Hannes: first cut for data Structures

2007-11-24T13:12:15Z

first cut for data Structures

Neue Seite

= Heaps =

* [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for A*-Search / Dijkstra
* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
'''However, practice shows that'''...
Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)). Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%.

== Fibonacci heap ==

<pre>
--- SPF-stats for 203 nodes, 335 routes (total/init/run/route/kern/cleanup):,, 237,
--- SPF-stats for 203 nodes, 337 routes (total/init/run/route/kern/cleanup):,, 238,
--- SPF-stats for 203 nodes, 337 routes (total/init/run/route/kern/cleanup):,, 238,
--- SPF-stats for 203 nodes, 339 routes (total/init/run/route/kern/cleanup):,, 239,
--- SPF-stats for 203 nodes, 339 routes (total/init/run/route/kern/cleanup):,, 238,
--- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 240,
--- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 236,
--- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 238,
--- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 238,
--- SPF-stats for 203 nodes, 345 routes (total/init/run/route/kern/cleanup):,, 239,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238,
--- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 238,

== AVL heap ==

AVL heap:
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 143,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 144,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 145,
--- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 144,
--- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 145,
--- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145,
--- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145,
--- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 142,
--- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 146,
</pre>

The following complexities<ref>
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
MIT Press / McGraw-Hill.
</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.

{| class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
|- style="background-color:#e9e9e9" |
! Operation
! [[Wikipedia:Binary heap|Binary]]
! [[Wikipedia:Binomial heap|Binomial]]
! [[Wikipedia:Fibonacci heap|Fibonacci]]
|-
| createHeap
|| Θ(1)
|| Θ(1)
|| Θ(1)
|-
| findMin
|| Θ(1)
|| O(lg ''n'') or Θ(1)
|| Θ(1)
|-
| deleteMin
|| Θ(lg ''n'')
|| Θ(lg ''n'')
|| O(lg ''n'')
|-
| insert
|| Θ(lg ''n'')
|| O(lg ''n'')
|| Θ(1)
|-
| decreaseKey
|| Θ(lg ''n'')
|| Θ(lg ''n'')
|| Θ(1)
|-
| merge
|| Θ(''n'')
|| O(lg ''n'')
|| Θ(1)
|}

== other interesting data structures not directly related ==
* [[Wikipedia:Data_Structures]] general overview. Good entry point for trees: [[Wikipedia:Binary_tree]]
* [http://www.nist.gov/dads/ NIST Directory of Data Structures] has a very extensive overview
* [http://www.google.com/search?client=safari&rls=en&q=Optimal+Worst-Case+Operations+for+Implicit+Cache-Oblivious+Search+Trees&ie=UTF-8&oe=UTF-8 succinct datastructures (trees)]
* [http://blogs.msdn.com/devdev/archive/2005/12/05/500171.aspx succinct datastructures overview]
* [http://en.wikipedia.org/wiki/Trie Tries]
* [http://www-users.cs.umn.edu/~saad/PS/iter1.pdf sparse matrices]
* look at [http://users.footprints.net/~kaz/kazlib.html kazlib] from IS-IS ??

==See also==
*[[Wikibooks:Data Structures/Min and Max Heaps|Heaps at wikibooks]]

@@ Zeile 1: / Zeile 1: @@
 = Heaps =
-* [[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for A*-Search / Dijkstra
+[[Wikipedia:Heap (data_structure)|Heap]] ... We need good heaps/priority queues for Dijkstra path exploration (relax function)
-* especially the [[Wikipedia:Fibonacci_heap|Fibonacci Heap]] has a to my knowledge the very best asymptotic complexity of O(1) almost everywhere.
-'''However, practice shows that'''...
-Currently as of 0.51pre we use a AVL tree which has complexity O(log(n)).
-Hannes tested the fibheap package from gcc and found out that in our networks (~ 200 nodes) the AVL tree heap implementation still beats the fibonacci heap by 60%. all results are in us based on a Intel celeron running at 1300 Mhz.
-−
-== Fibonacci heap ==
-−
-<pre>
---- SPF-stats for 203 nodes, 335 routes (total/init/run/route/kern/cleanup):,, 237,
---- SPF-stats for 203 nodes, 337 routes (total/init/run/route/kern/cleanup):,, 238,
---- SPF-stats for 203 nodes, 337 routes (total/init/run/route/kern/cleanup):,, 238,
---- SPF-stats for 203 nodes, 339 routes (total/init/run/route/kern/cleanup):,, 239,
---- SPF-stats for 203 nodes, 339 routes (total/init/run/route/kern/cleanup):,, 238,
---- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 240,
---- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 236,
---- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 238,
---- SPF-stats for 203 nodes, 341 routes (total/init/run/route/kern/cleanup):,, 238,
---- SPF-stats for 203 nodes, 345 routes (total/init/run/route/kern/cleanup):,, 239,
---- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238,
---- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238,
---- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238,
---- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238,
---- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 238,
-</pre>
-−
-== AVL heap ==
-−
-<pre>
-AVL heap:
---- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 143,
---- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142,
---- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142,
---- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 144,
---- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 145,
---- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145,
---- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142,
---- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 142,
---- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 144,
---- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 145,
---- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145,
---- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 145,
---- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 142,
---- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 146,
-</pre>
-−
 The following complexities<ref>
@@ Zeile 90: / Zeile 45: @@
 || Θ(1)
 |}
 == other interesting data structures not directly related ==

@@ Zeile 25: / Zeile 25: @@
 --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 238,
 --- SPF-stats for 203 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 238,
 </pre>
-−
-−
-−
-The following complexities<ref>
-Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms.
-MIT Press / McGraw-Hill.
-</ref> are worst-case for binary and binomial heaps and [[Wikipedia:Amortized analysis|amortized complexity]] for Fibonacci heap. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see [[Wikipedia:Big O notation]]). Function names assume a min-heap.
-−
-{|  class="toccolours" border="1" cellpadding="4" style="border-collapse:collapse"
-|- style="background-color:#e9e9e9" |
-! Operation
-! [[Wikipedia:Binary heap|Binary]]
-! [[Wikipedia:Binomial heap|Binomial]]
-! [[Wikipedia:Fibonacci heap|Fibonacci]]
-|-
-| createHeap
-|| Θ(1)
-|| Θ(1)
-|| Θ(1)
-|-
-| findMin
-|| Θ(1)
-|| O(lg ''n'') or Θ(1)
-|| Θ(1)
-|-
-| deleteMin
-|| Θ(lg ''n'')
-|| Θ(lg ''n'')
-|| O(lg ''n'')
-|-
-| insert
-|| Θ(lg ''n'')
-|| O(lg ''n'')
-|| Θ(1)
-|-
-| decreaseKey
-|| Θ(lg ''n'')
-|| Θ(lg ''n'')
-|| Θ(1)
-|-
-| merge
-|| Θ(''n'')
-|| O(lg ''n'')
-|| Θ(1)
-|}
-−
 == AVL heap ==
 AVL heap:
 --- SPF-stats for 203 nodes, 346 routes (total/init/run/route/kern/cleanup):,, 143,
@@ Zeile 108: / Zeile 46: @@
 --- SPF-stats for 202 nodes, 347 routes (total/init/run/route/kern/cleanup):,, 146,
 </pre>