In typical applications, a priority queue is used to execute a
sequence of n insert, m decrease, and n deletemin
operations, starting with an empty structure. We study the performance
of different priority queues for this type of operation sequences both
theoretically and experimentally. In particular, we focus on weak
heaps, weak queues, and their relaxed variants. We prove that for
relaxed weak heaps the execution of any such sequence requires at most
2 m + 1.5 n lg n element comparisons. This improves over
the best bound, at most 2 m + 2.89 n lg n element
comparisons, known for the existing variants of Fibonacci heaps. We
programmed six members of the weakheap family of priority queues.
For random data sets, experimental results show that nonrelaxed versions are
performing best and that rankrelaxed versions are slightly faster than
runrelaxed versions. Compared to weakheap variants, the corresponding
weakqueue variants are slightly better in time but not in the number of element comparisons.
