Data Structures and Algorithms

Aus FunkFeuer Wiki
Wechseln zu: Navigation, Suche

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)

other interesting data structures not directly related

See also