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.gif>PDF (208 kB)  
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.gif>HTML (Slides)  
  author = {Stefan Edelkamp and Amr Elmasry and Jyrki Katajainen and Armin
  title = {Weak heaps and friends: {R}ecent developments},
  booktitle = {Proceedings of the 24th International Workshop on Combinatorial
  series = {Lecture Notes in Computer Science},
  volume = {8288},
  publisher = {Springer-Verlag},
  year = {2013},
  pages = {1--6},
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 22.05.2015.