| A catalogue of algorithms for building weak heaps | |
| Authors: | Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen |
| Published in: | Proceedings of the 23nd International Workshop on Combinatorial Algorithms, Lecture Notes in Computer Science 7643, Springer-Verlag (2012), 249-262 |
| Full text: |  PDF (297 kB) |
| DOI: | 10.1007/978-3-642-35926-2_27 |
| Copyright: | © Springer-Verlag |
| Abstract: | An array-based weak heap is an efficient data structure for realizing an elementary priority queue. In this paper we focus on the construction of a weak heap. Starting from a straightforward algorithm, we end up with a catalogue of algorithms that optimize the standard algorithm in different ways. As the optimization criteria, we consider how to reduce the number of instructions, branch mispredictions, cache misses, and element moves. We also consider other approaches for building a weak heap: one based on repeated insertions and another relying on a non-standard memory layout. For most of the algorithms considered, we also study their effectiveness in practice. |
| Related: |  HTML (Source code) HTML (Journal article) |
| BibLATEX: | @inproceedings{EEK2012cC,
author = {Stefan Edelkamp and Amr Elmasry and Jyrki Katajainen},
title = {A catalogue of algorithms for building weak heaps},
booktitle = {Proceedings of the 23nd International Workshop on Combinatorial
Algorithms},
series = {Lecture Notes in Computer Science},
volume = {7643},
publisher = {Springer-Verlag},
year = {2012},
pages = {249--262},
}
|