https://github.com/sfrank/minheap.git
git clone 'https://github.com/sfrank/minheap.git'
(ql:quickload :minheap)
This project contains several heap data structures with priority queue and melding functionality. The heaps are hard-wired to min-heap only functionality on fixnum keys as I needed maximum performance for this use case. Since key comparison is in general limited to one or two places for every data structure variant only, an extension/re-use for max-heap functionality should be trivial.
Implemented heap data structures and their properties are collected in the table below.
Executive summary: for almost all cases the ‘pairing heap’ should give you the best performance. The ‘rank pairing heap’ has slightly worse overall performance but better worst case behaviour.
The different heap data structures posess the following computational complexities (amortized complexity is annotated with a ‘*’):
binary heap: - insert O(lg n) - find/peek min O(1) - delete min O(lg n) - delete node O(lg n) - decrease key O(lg n) - meld O(lg n)
splay heap: - insert O(lg n)* - find/peek min O(lg n)* - delete min O(lg n)* - delete node O(lg n)* - decrease key N/A - meld N/A
fibonacci heap: - insert O(1)* - find/peek min O(1)* - delete min O(lg n)* - delete node O(lg n)* - decrease key O(1)* - meld O(1)*
pairing heap and variants: - insert O(1)* - find/peek min O(1)* - delete min O(lg n)* - delete node O(lg n)* - decrease key O(1)* - meld O(1)*
violation heap: - insert O(1)* - find/peek min O(1)* - delete min O(lg n)* - delete node O(lg n)* - decrease key O(1)* - meld O(1)*