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, rank-relaxed weak heap, rank-relaxed weak queue, run-relaxed weak heap, and run-relaxed weak queue. Frameworks made policy-based benchmarking possible. We carried out extensive benchmarking with Dijkstra’s algorithm to compute shortest-path distances, and some synthetic data sets exploring the performance of these data structures in a worst-case scenario.

In its standard form a weak heap is implemented using an array. For a weak heap of size n, insert, decrease, and delete-min operations all take O(lg n) time in the worst case. By relying on a pointer-based implementation and by allowing a logarithmic number of nodes to break weak-heap ordering, insert and decrease operations can be supported in O(1) worst-case time. For any sequence of insert, decrease, and delete-min operations, the bound obtainable for the number of element comparisons performed by a rank-relaxed 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, non-relaxed versions performed best and rank-relaxed versions were slightly faster than run-relaxed versions. Compared to weak-heap variants, the corresponding weak-queue variants were slightly better in time but not in the number of element comparisons. For worst-case data sets, non-relaxed versions were slow for decrease and weak-queue variants were slightly faster than weak-heap variants. For insert, the logarithmic worst-case was hardy visible for weak heaps, whereas for relaxed versions the overhead caused by complicated transformations was clearly visible. For delete-min, all six data structures performed well. As a conclusion, we had to admit that the progress made by us was mainly analytical.

@report{EEK2011cS,
  author = {Stefan Edelkamp and Amr Elmasry and Jyrki Katajainen},
  title = {Weak-heap and weak-queue frameworks: {S}ource code},
  type = {CPH STL report},
  number = {2011-2},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {2011--2012},
  pagetotal = {81},
}