Multipartite priority queues

ABSTRACT

We introduce a framework for reducing the number of element comparisons performed in priority-queue operations. In particular, we give a priority queue which guarantees the worst-case cost of O(1) per minimum finding and insertion, and the worst-case cost of O(log n) with at most log n + O(1) element comparisons per deletion, improving the bound of 2 log n + O(1) known for binomial queues. Here, n denotes the number of elements stored in the data structure prior to the operation in question, and log n equals log₂(max {2, n}). As an immediate application of the priority queue developed, we obtain a sorting algorithm that is optimally adaptive with respect to the inversion measure of disorder, and that sorts a sequence having n elements and I inversions with at most n log (I/n) + O(n) element comparisons.

REFERENCES

• 1: Andrej Brodnik , Svante Carlsson , Erik D. Demaine , J. Ian Munro , Robert Sedgewick, Resizable Arrays in Optimal Time and Space, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.37-48, August 11-14, 1999
• 2: Brönnimann, H., Katajainen, J., and Morin, P. 2007. Putting your data structure on a diet. CPH STL Rep. 2007-1, Department of Computing, University of Copenhagen.
• 3: Brown, M. R. 1978. Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7, 3, 298--319.
• 4: Svante Carlsson, An optimal algorithm for deleting the roof of a heap, Information Processing Letters, v.37 n.2, p.117-120, Jan. 31, 1991 [doi>10.1016/0020-0190(91)90144-7]
• 5: Svante Carlsson , J. Ian Munro , Patricio V. Poblete, An implicit binomial queue with constant insertion time, No. 318 on SWAT 88: 1st Scandinavian workshop on algorithm theory, p.1-13, January 1988, Halmstad, Sweden
• 6: Michael J. Clancy , Donald E. Knuth, A programming and problem-solving seminar, Stanford University, Stanford, CA, 1977
• 7: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 8: James R. Driscoll , Harold N. Gabow , Ruth Shrairman , Robert E. Tarjan, Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation, Communications of the ACM, v.31 n.11, p.1343-1354, Nov. 1988 [doi>10.1145/50087.50096]
• 9: Amr Elmasry, Priority Queues, Pairing, and Adaptive Sorting, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.183-194, July 08-13, 2002
• 10: Elmasry, A. 2003a. Distribution-sensitive binomial queues. In Proceedings of the 8th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 2748. Springer, 103--113.
• 11: Elmasry, A. 2003b. Three sorting algorithms using priority queues. In Proceedings of the 14th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 2906. Springer, 209--220.
• 12: Elmasry, A. 2004. Layered heaps. In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 3111. Springer, 212--222.
• 13: Amr Elmasry , Michael L. Fredman, Adaptive Sorting and the Information Theoretic Lower Bound, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.654-662, February 27-March 01, 2003
• 14: Amr Elmasry , Michael L. Fredman, Adaptive sorting: an information theoretic perspective, Acta Informatica, v.45 n.1, p.33-42, January 2008 [doi>10.1007/s00236-007-0061-0]
• 15: Vladmir Estivill-Castro , Derick Wood, A survey of adaptive sorting algorithms, ACM Computing Surveys (CSUR), v.24 n.4, p.441-476, Dec. 1992 [doi>10.1145/146370.146381]
• 16: Michael L. Fredman , Robert Sedgewick , Daniel D. Sleator , Robert E. Tarjan, The pairing heap: a new form of self-adjusting heap, Algorithmica, v.1 n.1, p.111-129, Jan. 1986 [doi>10.1007/BF01840439]
• 17: Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
• 18: Gaston H Gonnet , J Ian Munro, Heaps on heaps, SIAM Journal on Computing, v.15 n.4, p.964-971, Nov. 1986 [doi>10.1137/0215068]
• 19: John Iacono, Improved Upper Bounds for Pairing Heaps, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.32-45, July 05-07, 2000
• 20: Haim Kaplan , Nira Shafrir , Robert E. Tarjan, Meldable heaps and boolean union-find, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509990]
• 21: Kaplan, H. and Tarjan, R. E. 1999. New heap data structures. Tech. rep. TR-597-99, Department of Computer Science, Princeton University.
• 22: Haim Kaplan , Robert Endre Tarjan, Thin heaps, thick heaps, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-14, March 2008 [doi>10.1145/1328911.1328914]
• 23: Jyrki Katajainen , Bjarke Buur Mortensen, Experiences with the Design and Implementation of Space-Efficient Deques, Proceedings of the 5th International Workshop on Algorithm Engineering, p.39-50, August 28-31, 2001
• 24: Jyrki Katajainen , Fabio Vitale, Navigation piles with applications to sorting, priority queues, and priority deques, Nordic Journal of Computing, v.10 n.3, p.238-262, September 2003
• 25: Christos Levcopoulos , Ola Petersson, Adaptive heapsort, Journal of Algorithms, v.14 n.3, p.395-413, May 1993 [doi>10.1006/jagm.1993.1021]
• 26: Moffat, A. and Petersson, O. 1992. An overview of adaptive sorting. Australian Comput. J. 24, 2, 70--77.
• 27: Overmars, M. H. and van Leeuwen, J. 1981. Worst-Case optimal insertion and deletion methods for decomposable searching problems. Inf. Proc. Lett. 12, 4, 168--173.
• 28: Petersson, O. 1990. Adaptive sorting. Ph.D. thesis, Department of Computer Science, Lund University.
• 29: Schönhage, A., Paterson, M., and Pippenger, N. 1976. Finding the median. J. Comput. Syst. Sci. 13, 2, 184--199.
• 30: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 31: Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, v.21 n.4, p.309-315, April 1978 [doi>10.1145/359460.359478]
• 32: Jean Vuillemin, A unifying look at data structures, Communications of the ACM, v.23 n.4, p.229-239, April 1980 [doi>10.1145/358841.358852]
• 33: Williams, J. W. J. 1964. Algorithm 232: Heapsort. Comm. ACM 7, 6, 347--348.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Priority queues, constant factors, heaps, meticulous analysis