This is a work in progress to test the performance of different heap structures against each other.
Initial testing suggests that binary heaps are really good. With enough decrease key operations and a large enough heap, pairing and Fibonacci heaps gain parity; however, even on very dense small to mid sized graphs, binary heaps have a slight edge. Run times on my laptop approached one minute before pairing and Fibonacci heaps saw an advantage. Between those two, there doesn't seem to be a great difference in run time.
Check out the wiki.
- Binary
- Fibonacci
- Pairing
- Dijkstra's Single Source Shortest Path
- Sequential heap operations
The binary heap used is an implicit binary heap from Python's heap queue module.
The following sources were very helpful to make my pairing heap.
Largely copied from Introduction to Algorithms by Cormen et al., 2009.
- Redo these tests in C++
- Test more algorithms and graph classes
- Test more heaps/priority queues