Quelltext der Seite Data Structures and Algorithms

= 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%. 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>
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,
--- 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]]