Weak-heap and weak-queue frameworks: Source code
Authors:Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Publication:CPH STL report 2011-2, Department of Computer Science, University of Copenhagen (2011–2012), 81 pp.
Full text:<pdf.gif>PDF (952 kB)  
Abstract:This report is an electronic appendix to our paper "The weak-heap family of priority queues in theory and praxis" presented at the 18th Computing: Australasian Theory Symposium that was held in Melbourne in January-February 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, 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.

Related:<html.gif>HTML (Conference paper)  <html.gif>HTML (Journal article)  <html.gif>HTML (tar archive)  
  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},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 2019-10-05.