The weak-heap family of priority queues in theory and praxis

TY - GEN

T1 - The weak-heap family of priority queues in theory and praxis

AU - Edelkamp, Stefan

AU - Elmasry, Amr Ahmed Abd Elmoneim

AU - Katajainen, Jyrki

N1 - Conference code: 18

PY - 2012

Y1 - 2012

N2 - 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 2m + 1:5n lg n element comparisons. This improves over the best bound, at most 2m + 2:89n 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.

AB - 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 2m + 1:5n lg n element comparisons. This improves over the best bound, at most 2m + 2:89n 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.

M3 - Article in proceedings

T3 - Conferences in Research and Practice in Information Technology

SP - 103

EP - 112

BT - Proceedings of the Eighteenth Computing: The Australasian Theory Symposium

A2 - Mestre, Julian

PB - Australian Computer Society

T2 - 18th Computing: The Australasian Theory Symposium

Y2 - 31 January 2012 through 3 February 2012

ER -