This report is an electronic appendix to our paper "The weakheap
family of priority queues in theory and praxis" presented at the 18th
Computing: Australasian Theory Symposium that was held in Melbourne in
JanuaryFebruary 2012. This report together with an accompanying
tar ball gives the source code used in the experiments
reported in that paper. We implemented weak heaps and their close relatives weak queues as
component frameworks that utilize the same collection of registries.
By varying the registries used, our frameworks provide implementations
for six different data structures: weak heap, weak queue, rankrelaxed
weak heap, rankrelaxed weak queue, runrelaxed weak heap, and
runrelaxed weak queue. Frameworks made policybased benchmarking
possible. We carried out extensive benchmarking with Dijkstraâ€™s
algorithm to compute shortestpath distances, and some synthetic data
sets exploring the performance of these data structures in a
worstcase scenario. In its standard form a weak heap is implemented using an array. For a
weak heap of size n, insert, decrease, and
deletemin operations all take O(lg n) time in the worst case. By
relying on a pointerbased implementation and by allowing a
logarithmic number of nodes to break weakheap ordering, insert and
decrease operations can be supported in O(1) worstcase time. For
any sequence of insert, decrease, and deletemin operations,
the bound obtainable for the number of element comparisons performed
by a rankrelaxed weak heap is the best for all known priority queues;
the bound is even better than that known for a Fibonacci heap. In our experiments, for random data sets, nonrelaxed versions
performed best and rankrelaxed versions were slightly faster than
runrelaxed versions. Compared to weakheap variants, the
corresponding weakqueue variants were slightly better in time but not
in the number of element comparisons. For worstcase data sets,
nonrelaxed versions were slow for decrease and weakqueue variants
were slightly faster than weakheap variants. For insert, the
logarithmic worstcase was hardy visible for weak heaps, whereas for
relaxed versions the overhead caused by complicated transformations
was clearly visible. For deletemin, all six data structures
performed well. As a conclusion, we had to admit that the progress
made by us was mainly analytical.
