In typical applications, a priority queue is used to execute a
sequence of n insert, m decrease, and n delete-min
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 weak-heap family of priority queues.
For random data sets, experimental results show that non-relaxed versions are
performing best and that rank-relaxed versions are slightly faster than
run-relaxed versions. Compared to weak-heap variants, the corresponding
weak-queue variants are slightly better in time but not in the number of element comparisons.