| Weak heaps and friends: Recent developments | |
| Authors: | Stefan Edelkamp, Amr Elmasry, Jyrki Katajainen, and Armin Weiß |
| Published in: | Proceedings of the 24th International Workshop on Combinatorial Algorithms, Lecture Notes in Computer Science 8288, Springer-Verlag (2013), 1-6 |
| Full text: |  PDF (208 kB) |
| DOI: | 10.1007/978-3-642-45278-9_1 |
| Copyright: | © Springer-Verlag GmbH Berlin Heidelberg |
| Abstract: | A weak heap is a variant of a binary heap where, for each node, the heap ordering is enforced only for one of its two children. In 1993, Dutton showed that this data structure yields a simple worst-case-efficient sorting algorithm. In this paper we review the refinements proposed to the basic data structure that improve the efficiency even further. Ultimately, minimum and insert operations are supported in O(1) worst-case time and extract-min operation in O(lg n) worst-case time involving at most lg n + O(1) element comparisons. In addition, we look at several applications of weak heaps. This encompasses the creation of a sorting index and the use of a weak heap as a tournament tree leading to a sorting algorithm that is close to optimal in terms of the number of element comparisons performed. By supporting insert operation in O(1) amortized time, the weak-heap data structure becomes a valuable tool in adaptive sorting leading to an algorithm that is constant-factor optimal with respect to several measures of disorder. Also, a weak heap can be used as an intermediate step in an efficient construction of binary heaps. For graph search and network optimization, a weak-heap variant, which allows some of the nodes to violate the weak-heap ordering, is known to be provably better than a Fibonacci heap. |
| Related: |  HTML (Slides) |
| BibLATEX: | @inproceedings{EEKW2013C,
author = {Stefan Edelkamp and Amr Elmasry and Jyrki Katajainen and Armin
Wei{\ss}},
title = {Weak heaps and friends: {R}ecent developments},
booktitle = {Proceedings of the 24th International Workshop on Combinatorial
Algorithms},
series = {Lecture Notes in Computer Science},
volume = {8288},
publisher = {Springer-Verlag},
year = {2013},
pages = {1--6},
}
|