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. Brodnik, A., Carlsson, S., Demaine, E. D., Munro, J. I., and Sedgewick, R. 1999. Resizable arrays in optimal time and space. In Proceedings of the 6th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 1663. Springer, 37--48.
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. Carlsson, S. 1991. An optimal algorithm for deleting the root of a heap. Inf. Proc. Lett. 37, 2, 117--120.
5. Carlsson, S., Munro, J. I., and Poblete, P. V. 1988. An implicit binomial queue with constant insertion time. In Proceedings of the 1st Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 318. Springer, 1--13.
6. Clancy, M. J. and Knuth, D. E. 1977. A programming and problem-solving seminar. Tech. rep. STAN-CS-77-606, Department of Computer Science, Stanford University.
7. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms, 2nd ed. The MIT Press.
8. Driscoll, J. R., Gabow, H. N., Shrairman, R., and Tarjan, R. E. 1988. Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Comm. ACM 31, 11, 1343--1354.
9. Elmasry, A. 2002. Priority queues, pairing, and adaptive sorting. In Proceedings of the 29th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 2380. Springer, 183--194.
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. Elmasry, A. and Fredman, M. L. 2003. Adaptive sorting and the information theoretic lower bound. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2607. Springer, 654--662.
14. Elmasry, A. and Fredman, M. L. 2008. Adaptive sorting: An information theoretic perspective. Acta Inform. 45, 1, 33--42.
15. Estivill-Castro, V. and Wood, D. 1992. A survey of adaptive sorting algorithms. ACM Comput. Surv. 24, 4, 441--476.
16. Fredman, M. L., Sedgewick, R., Sleator, D. D., and Tarjan, R. E. 1986. The pairing heap: A new form of self-adjusting heap. Algorithmica 1, 1, 111--129.
17. Gabow, H. N., Bentley, J. L., and Tarjan, R. E. 1984. Scaling and related techniques for geometry problems. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing. ACM, 135--143.
18. Gonnet, G. H. and Munro, J. I. 1986. Heaps on heaps. SIAM J. Comput. 15, 4, 964--971.
19. Iacono, J. 2000. Improved upper bounds for pairing heaps. In Proceedings of the 7th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 1851. Springer, 32--45.
20. Kaplan, H., Shafrir, N., and Tarjan, R. E. 2002. Meldable heaps and Boolean union-find. In Proceedings of the 34th ACM Symposium on Theory of Computing. ACM, 573--582.
21. Kaplan, H. and Tarjan, R. E. 1999. New heap data structures. Tech. rep. TR-597-99, Department of Computer Science, Princeton University.
22. Kaplan, H. and Tarjan, R. E. 2008. Thin heaps, thick heaps. ACM Trans Algor. 4, 1.
23. Katajainen, J. and Mortensen, B. B. 2001. Experiences with the design and implementation of space-efficient deques. In Proceedings of the 5th Workshop on Algorithm Engineering. Lecture Notes in Computer Science, vol. 2141. Springer, 39--50.
24. Katajainen, J. and Vitale, F. 2003. Navigation piles with applications to sorting, priority queues, and priority deques. Nordic J. Comput. 10, 3, 238--262.
25. Levcopoulos, C. and Petersson, O. 1993. Adaptive heapsort. J. Algor. 14, 3, 395--413.
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. Tarjan, R. E. 1983. Data Structures and Network Algorithms. SIAM.
31. Vuillemin, J. 1978. A data structure for manipulating priority queues. Comm. ACM 21, 4, 309--315.
32. Vuillemin, J. 1980. A unifying look at data structures. Comm. ACM 23, 4, 229--239.
33. Williams, J. W. J. 1964. Algorithm 232: Heapsort. Comm. ACM 7, 6, 347--348.

Index Terms

• Information systems

  • Data management systems

    • Data structures

  • Information storage systems

    • Record storage systems

      • Record storage alternatives

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Data types and structures

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

  • Theory and algorithms for application domains

    • Database theory

      • Data structures and algorithms for data management