Data Structures and Algorithms: Unterschied zwischen den Versionen
Hannes (Diskussion | Beiträge) (first cut for data Structures) |
Hannes (Diskussion | Beiträge) K (→Fibonacci heap) |
||
| Zeile 24: | Zeile 24: | ||
--- 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, | --- 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 == | ||
Version vom 24. November 2007, 14:13 Uhr
Inhaltsverzeichnis
Heaps
- Heap ... We need good heaps/priority queues for A*-Search / Dijkstra
- especially the 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
--- 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,
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 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.
| Operation | Binary | Binomial | 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 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.
| Operation | Binary | Binomial | 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) |
- Wikipedia:Data_Structures general overview. Good entry point for trees: Wikipedia:Binary_tree
- NIST Directory of Data Structures has a very extensive overview
- succinct datastructures (trees)
- succinct datastructures overview
- Tries
- sparse matrices
- look at kazlib from IS-IS ??
