Implementation of several advanced heap data structures with priority queue and meld functionality in Common Lisp
Common Lisp
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
test - add multi-root variant of a rank-pairing heap May 6, 2012
LICENCE add ASDF system definition and related corrections Apr 11, 2012
README spelling Jan 17, 2013
binary-heap.lisp making minheap compatible with Allegro mlisp Jun 4, 2016
fib-heap.lisp making minheap compatible with Allegro mlisp Jun 4, 2016
minheap-tests.asd - add multi-root variant of a rank-pairing heap May 6, 2012
minheap.asd - add multi-root variant of a rank-pairing heap May 6, 2012
pairing-heap-elmasri.lisp making minheap compatible with Allegro mlisp Jun 4, 2016
pairing-heap-listbased.lisp making minheap compatible with Allegro mlisp Jun 4, 2016
pairing-heap.lisp
rank-pairing-heap-clist.lisp making minheap compatible with Allegro mlisp Jun 4, 2016
rank-pairing-heap.lisp
splay-heap.lisp making minheap compatible with Allegro mlisp Jun 4, 2016
violation-heap.lisp making minheap compatible with Allegro mlisp Jun 4, 2016

README

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)*