Policy-Based Benchmarking of Weak Heaps and Their Relatives

摘要

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(l), and a run-relaxed weak queue that of both insert and decrease to O(l). 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.