Data Structures and Algorithms

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%. all results are in us based on a Intel celeron running at 1300 Mhz.

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)

other interesting data structures not directly related

• 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 ??

See also

• Heaps at wikibooks