Min-max heaps and generalized priority queues

ABSTRACT

A simple implementation of double-ended priority queues is presented. The proposed structure, called a min-max heap, can be built in linear time; in contrast to conventional heaps, it allows both FindMin and FindMax to be performed in constant time; Insert, DeleteMin, and DeleteMax operations can be performed in logarithmic time. Min-max heaps can be generalized to support other similar order-statistics operations efficiently (e.g., constant time FindMedian and logarithmic time DeleteMedian); furthermore, the notion of min-max ordering can be extended to other heap-ordered structures, such as leftist trees.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Atkinson. M.D., Sack, J.-R.. Santoro, N., and Strothotte, Th. An efficient. implicit double-ended priority queue. Tech. Rep. SCS-TR-55, School of Computer Science, Carleton University, Ottawa, Ont.. Canada, Ju!y 1984.
• 3: Atkinson. M.D., Sack, J.-R., Santoro, N., and Strotbotte, Th. Min-max heaps, order-statistic trees and their application to the Course- Marks problem. In Proceedings of Nineteenth Conference on Information and Syskm Sciences, Baltimore, Md., (Mar. 19851. 160-165.
• 4: Robert W. Floyd, Algorithm 245: Treesort, Communications of the ACM, v.7 n.12, p.701, Dec. 1964 [doi>10.1145/355588.365103]
• 5: Gaston H. Gonnet, Handbook of Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 6: Gaston H. Gonnet , J. Ian Munro, Heaps on Heaps, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.282-291, July 12-16, 1982
• 7: Azmeena Hasham, A new class of priority queue organizations, 1986
• 8: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 9: J. Ian Munro , Hendra Suwanda, Implicit data structures (Preliminary Draft), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.108-117, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804404]
• 10: Sack, J.-R., and Strothotte, Th. An algorithm for merging heaps. Acta Inform. 22,(1985), 171-186.
• 11: Strothotte, Th.. and Sack, J.-R. Heaps in heaps. Congressus Numerantium, 49 (1985). 223-235.
• 12: Williams, J.W.J. Algorithm 232. Commun. ACM 7, 6 (June 1964), 347-348.

INDEX TERMS

Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Theory