Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) amortized time, where n is an upper bound on the number of elements in the priority queue, can be converted into a priority queue data structure that also supports fast meld operations with essentially no increase in the amortized cost of the other operations. More specifically, the new data structure supports insert, meld and find-min operations in O(1) amortized time, and delete operations in O(pq(n) + α(n)) amortized time, where α(n) is a functional inverse of the Ackermann function, and where n this time is the total number of operations performed on all the priority queues. The construction is very simple. The meldable priority queues are obtained by placing a nonmeldable priority queues at each node of a union-find data structure. We also show that when all keys are integers in the range [1, N], we can replace n in the bound stated previously by min{n, N}.Applying this result to the nonmeldable priority queue data structures obtained recently by Thorup [2002b] and by Han and Thorup [2002] we obtain meldable RAM priority queues with O(log log n) amortized time per operation, or O(&sqrt;log log n) expected amortized time per operation, respectively. As a by-product, we obtain improved algorithms for the minimum directed spanning tree problem on graphs with integer edge weights, namely, a deterministic O(m log log n)-time algorithm and a randomized O(m&sqrt;log log n)-time algorithm. For sparse enough graphs, these bounds improve on the O(m + n log n) running time of an algorithm by Gabow et al. [1986] that works for arbitrary edge weights.

REFERENCES

• 1: Alstrup, S., Gørtz, I., Rauhe, T., Thorup, M., and Zwick, U. 2005. Union-find with constant time deletions. In Proceedings of the 32th International Colloquium on Automata, Languages and Programming (ICALP). 78--89.
• 2: Stephen Alstrup , Thore Husfeldt , Theis Rauhe , Mikkel Thorup, Black box for constant-time insertion in priority queues (note), ACM Transactions on Algorithms (TALG), v.1 n.1, p.102-106, July 2005 [doi>10.1145/1077464.1077471]
• 3: Bock, F. 1971. An algorithm to construct a minimum directed spanning tree in a directed network. In Developments in Operations Research. Gordon and Breach, New York, 29--44.
• 4: Jonathan D. Bright, Range-restricted mergeable priority queues, Information Processing Letters, v.47 n.3, p.159-164, Sept. 14, 1993 [doi>10.1016/0020-0190(93)90240-A]
• 5: Camerini, P., Fratta, L., and Maffioli, F. 1979. A note on finding optimum branchings. Networks 9, 309--312.
• 6: 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]
• 7: Chu, Y., and Liu, T. 1965. On the shortest arborescence of a directed graph. Sci. Sinica 14, 1396--1400.
• 8: Comrie, L. 1929. The Hollerith and Powers tabulating machines. Office Machinary Users' Association, Ltd. 25--37.
• 9: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 10: Dijkstra, E. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269--271.
• 11: Dumey, A. 1956. Indexing for rapid random access memory systems. Comput. Automation 5, 12, 6--9.
• 12: Edmonds, J. 1967. Optimum branchings. J. Res. Nat. Bur. Stand. 71B, 233--240.
• 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: 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]
• 17: 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]
• 18: 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
• 19: 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]
• 20: 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
• 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: Karp, R. 1971. A simple derivation of Edmonds' algorithm for optimum branchings. Networks 1, 265--272.
• 23: Mendelson, R., Tarjan, R., Thorup, M., and Zwick, U. 2004a. Melding priority queues. In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT). 223--235.
• 24: Ran Mendelson , Mikkel Thorup , Uri Zwick, Meldable RAM priority queues and minimum directed spanning trees, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 25: Seth Pettie , Vijaya Ramachandran, An optimal minimum spanning tree algorithm, Journal of the ACM (JACM), v.49 n.1, p.16-34, January 2002 [doi>10.1145/505241.505243]
• 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: Tarjan, R. 1977. Finding optimum branchings. Networks 7, 25--35.
• 28: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 29: Tarjan, R. 1985. Amortized computational complexity. SIAM J. Algebraic Discrete Meth. 6, 306--318.
• 30: Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984 [doi>10.1145/62.2160]
• 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: Thorup, M. 2002b. Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations. J. Algorithms 42, 2, 205--230.
• 33: Mikkel Thorup, On AC⁰ implementations of fusion trees and atomic heaps, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 34: van Emde Boas, P., Kaas, R., and Zijlstra, E. 1977. Design and implementation of an efficient priority queue. Mathemat. Syst. Theo. 10, 99--127.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
Priority queues, disjoint set union, heaps, minimum directed spanning trees, optimum branchings, union-find, word RAM model