Data Structures and Algorithms
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 ??
