Heaps for Racket

This is a functional implementation of heaps viz. Binomial and Fibonacci. For development, the following set of materials were referred:

• Kozen
• Kevin Wayne's lecture notes
• Fredman & Tarjan. "Fibonacci heaps and their uses in improved network optimization algorithms"
• Vuillemin, "A data structure for manipulating priority queues"

Brief description

Binomial heap is a collection of heap-ordered binomial trees with a pointer min to the tree whose root has minimum value. They are handy for quick merging of multiple heaps, and deleting the node with the minimal value.

Fibonacci heaps, are a generalization of Binomial heaps allowing additional features other than those in binomial heaps. Specifically, they allow deletion of a node from the heap, and modification of the value of a node in the heap. For a more detailed description, refer to materials cited above.

The whitepaper is available here.

High resolution figures in the whitepaper for easy viewing are available here:

• Binomial Heaps Anomaly(linear)
• Binomial Heaps Anomaly(quadratic)
• Fibonacci Heaps (insert)
• Fibonacci Heaps (meld)
• Fibonacci Heaps (delete)
• Fibonacci Heaps (decrement)
• Binary vs Fibonacci (findmin)
• Binary vs Fibonacci (deletemin)

Usage

Clone repository using:

git clone git@github.com:ajauhri/rkt-heaps.git	

Open racket in terminal or add to source, using:

(require "$RKT_HEAPS_HOME/src/binomial.rkt")
(require "$RKT_HEAPS_HOME/src/fibonacci.rkt")

, where $RKT_HEAPS_HOME is the root directory for the downloaded source.

All core operations with examples are documented on the following pages:

• Binomial docs
• Fibonacci docs

Files under benchmarks folder also provide a good set of examples on the usage of this API.

Benchmarks

Benchmarks can be easily generated for all core functions using files here. Any one of such files can be run with following arguments:

• ssize - the starting size of the heap in the benchmark
• esize - the largest size of the heap to be included in the benchmark

For example, ./delete_benchmarks.rkt 10 100 will have timing of operations measured over heap sizes - 10 20 30 40 50 60 70 80 90 100 over the total expected cost (in this case it is O(nlog n)). It will generate a pdf file titled as delete_benchmarks_10_100.pdf.

Running the test suite

Test cases can be found here, and individual test suite can be run using:

cd rkt-heaps/tests/	
./binomial_tests
./binomial_helper_tests
./fibonacci_tests

All tests can be run using:

./run_all_tests.rkt