Meldable RAM priority queues and minimum directed spanning trees

ABSTRACT

We consider the implementation of meldable priority queues with integer keys in the RAM model. We present two new general techniques for transforming non-meldable priority queues into meldable ones. These transformations can be described symbolically as:non-meldable priority queue +union-find ← meldable priority queuenon-meldable priority queue +slow meldable priority queue ←faster meldable priority queueUsing the first transformation to combine a recent non-meldable RAM priority queue of Thorup with the classical union-find data structure we obtain a meldable RAM priority queue with an amortized cost of O(log log n·α(n)) per operation, where α(n) = α(n, n) is the inverse Ackermann function. Using instead a randomized priority queue of Han and Thorup we obtain an expected amortized cost of O(√(log log n) · α(n)) per operation. The second transformation yields slower meldable priority queues, but the obtained queues can support the insert, find-min and decrease-key operations in constant time. In particular, by combining a randomized "atomic-heap" of Thorup with, e.g., the classical Fibonacci heaps of Fredman and Tarjan, we obtain, for every fixed ε > 0, a meldable priority queue with an expected amortized cost of O(1) for each insert, find-min and decrease-key operation, and an expected amortized cost of O((log n)^1/2+ε) for each delete or meld operation.Using the meldable priority queues of the first type, we obtain improved algorithms for finding minimum directed spanning trees in graphs with integer edge weights: a deterministic O(m · log log n · α(n)) time algorithm and a randomized O(m · √(log log n) · α(n)) expected time algorithm. These bounds improve, for very sparse graphs, on the O(m + n log n) running time of an algorithm by Gabow, Galil, Spencer and Tarjan that works for arbitrary edge weights.

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: Ravindra K. Ahuja , Kurt Mehlhorn , James Orlin , Robert E. Tarjan, Faster algorithms for the shortest path problem, Journal of the ACM (JACM), v.37 n.2, p.213-223, April 1990 [doi>10.1145/77600.77615]
• 3: {Boc71} F. Bock. An algorithm to construct a minimum directed spanning tree in a directed network. in: Developments in Operations Research, Gordon and Breach, New York, pages 29--44, 1971.
• 4: Gerth Stølting Brodal, Worst-case efficient priority queues, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.52-58, January 28-30, 1996, Atlanta, Georgia, United States
• 5: {CFM79} P. M. Camerini, L. Fratta, and F. Maffioli. A note on finding optimum branchings. Networks, 9:309--312, 1979.
• 6: Boris V. Cherkassky , Andrew V. Goldberg , Craig Silverstein, Buckets, Heaps, Lists, and Monotone Priority Queues, SIAM Journal on Computing, v.28 n.4, p.1326-1346, Aug. 1999 [doi>10.1137/S0097539796313490]
• 7: Bernard Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity, Journal of the ACM (JACM), v.47 n.6, p.1028-1047, Nov. 2000 [doi>10.1145/355541.355562]
• 8: {CL65} Y. J. Chu and T. H. Liu. On the shortest arborescence of a directed graph. Sci. Sinica, 14:1396--1400, 1965.
• 9: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 10: {Dij59} E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.
• 11: Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm MeyerAuf Der, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM Journal on Computing, v.23 n.4, p.738-761, Aug. 1994 [doi>10.1137/S0097539791194094]
• 12: {Edm67} J. Edmonds. Optimum branchings. J. Res. Nat. Bur. Standards, 71B:233--240, 1967.
• 13: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 14: Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
• 15: Michael L. Fredman , Dan E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Journal of Computer and System Sciences, v.48 n.3, p.533-551, June 1994 [doi>10.1016/S0022-0000(05)80064-9]
• 16: Harold N. Gabow , Zvi Galil , Thomas H. Spencer, Efficient implementation of graph algorithms using contraction, Journal of the ACM (JACM), v.36 n.3, p.540-572, July 1989 [doi>10.1145/65950.65954]
• 17: H N Gabow , Z Galil , T Spencer , R E Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, v.6 n.2, p.109-122, 1986 [doi>10.1007/BF02579168]
• 18: Yijie Han, Deterministic sorting in O(nlog log n) time and linear space, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509993]
• 19: Yijie Han , Mikkel Thorup, Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.135-144, November 16-19, 2002
• 20: {Kar71} R. M. Karp. A simple derivation of Edmonds' algorithm for optimum branchings. Networks, 1:265--272, 1971.
• 21: David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995 [doi>10.1145/201019.201022]
• 22: 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]
• 23: Haim Kaplan , Nira Shafrir , Robert E. Tarjan, Union-find with deletions, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.19-28, January 06-08, 2002, San Francisco, California
• 24: {Pri57} R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389--1401, 1957.
• 25: Rajeev Raman, Recent results on the single-source shortest paths problem, ACM SIGACT News, v.28 n.2, p.81-87, June 1997 [doi>10.1145/261342.261352]
• 26: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 27: {Tar77} R. E. Tarjan. Finding optimum branchings. Networks, 7:25--35, 1977.
• 28: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 29: {Tar85} R. E. Tarjan. Amortized computational complexity. SIAM Journal on Algebraic and Discrete Methods, 6:306--318, 1985.
• 30: Mikkel Thorup, On RAM Priority Queues, SIAM Journal on Computing, v.30 n.1, p.86-109, 2000 [doi>10.1137/S0097539795288246]
• 31: Mikkel Thorup, Equivalence between Priority Queues and Sorting, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.125-134, November 16-19, 2002
• 32: Mikkel Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780566]
• 33: {van77} P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6(3):80--82, 1977.
• 34: {vKZ77} P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99--127, 1977.
• 35: {Wil83} D. Willard. Log-logarithmic worst case range queries are possible in space O(N). Inform. Process Lett., pages 81--84, 1983.