Weak Heaps and Friends: Recent Developments

详细信息    查看全文

• 作者：Stefan Edelkamp (17)
  Amr Elmasry (18)
  Jyrki Katajainen (19)
  Armin Wei? (20)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：8288
• 期：1
• 页码：7-13
• 全文大小：146KB
• 作者单位：Stefan Edelkamp (17)
  Amr Elmasry (18)
  Jyrki Katajainen (19)
  Armin Wei? (20)
  
  17. Faculty 3—Mathematics and Computer Science, University of Bremen, P.O. Box 330 440, 28334, Bremen, Germany
  18. Department of Computer Engineering and Systems, Alexandria University, Alexandria, 21544, Egypt
  19. Department of Computer Science, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen East, Denmark
  20. Institute for Formal Methods in Computer Science, University of Stuttgart, Universit?tstra?e 38, 70569, Stuttgart, Germany
  
• ISSN：1611-3349

文摘

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.