Policy-based benchmarking of weak heaps and their relatives
Authors:Asger Bruun, Stefan Edelkamp, Jyrki Katajainen, and Jens Rasmussen
Published in:Proceedings of the 9th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 6049, Springer-Verlag (2010), 424-435
Full text:<pdf.gif>PDF (418 kB)  
Copyright:© Springer-Verlag

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.

Related:<html.gif>HTML (Source code)  
  author = {Asger Bruun and Stefan Edelkamp and Jyrki Katajainen and Jens
  title = {Policy-based benchmarking of weak heaps and their relatives},
  booktitle = {Proceedings of the 9th International Symposium on Experimental
  series = {Lecture Notes in Computer Science},
  volume = {6049},
  publisher = {Springer-Verlag},
  year = {2010},
  pages = {424--435},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.