In this paper we describe an experimental study where we evaluated the practical efficiency of three worst-case efficient priority queues: 1) a weak heap that is a binary tree fulfilling half-heap ordering, 2) a weak queue that is a forest of perfect weak heaps, and 3) a run-relaxed weak queue that extends a weak queue by allowing some nodes to violate half-heap ordering. All these structures support delete and delete-min in logarithmic worst-case time. A weak heap supports insert and decrease in logarithmic worst-case time, whereas a weak queue reduces the worst-case running time of insert to O(1), and a run-relaxed weak queue that of both insert and decrease to O(1). As competitors to these structures, we considered a binary heap, a Fibonacci heap, and a pairing heap. Generic programming techniques were heavily used in the code development. For benchmarking purposes we developed several component frameworks that could be instantiated with different policies.

@inproceedings{BEKR2010C,
  author = {Asger Bruun and Stefan Edelkamp and Jyrki Katajainen and Jens
    Rasmussen},
  title = {Policy-based benchmarking of weak heaps and their relatives},
  booktitle = {Proceedings of the 9th International Symposium on Experimental
    Algorithms},
  series = {Lecture Notes in Computer Science},
  volume = {6049},
  publisher = {Springer-Verlag},
  year = {2010},
  pages = {424--435},
}