Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation

ABSTRACT

The relaxed heap is a priority queue data structure that achieves the same amortized time bounds as the Fibonacci heap—a sequence of m decrease_key and n delete_min operations takes time O(m + n log n). A variant of relaxed heaps achieves similar bounds in the worst case—O(1) time for decrease_key and O(log n) for delete_min. Relaxed heaps give a processor-efficient parallel implementation of Dijkstra's shortest path algorithm, and hence other algorithms in network optimization. A relaxed heap is a type of binomial queue that allows heap order to be violated.

REFERENCES

• 1: Awerbuch, B. and Shiloach, Y. New connectivity and MSF algorithms for Ultracomputer and PRAM. In Proceedings of the IEEE 1983 International Conference on Parallel Processing (1983), pp. 175-179.
• 2: Brown, M.R. Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7, 3 (1978), 298-319.
• 3: 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]
• 4: Harold N. Gabow, Scaling algorithms for network problems, Journal of Computer and System Sciences, v.31 n.2, p.148-168, Sept. 1985 [doi>10.1016/0022-0000(85)90039-X]
• 5: 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]
• 6: Harold Gabow , Robert Tarjan, Almost-optimum speed-ups of algorithms for bipartite matching and related problems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.514-527, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62263]
• 7: A. Goldberg , R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.7-18, January 1987, New York, New York, United States [doi>10.1145/28395.28397]
• 8: Kwan, S.C., and Ruzzo, W.L. Adaptive parallel algorithms for finding minimum spanning trees. In Proceedings of the IEEE 1984 International Conference on Parallel Processi,g, 1984, pp. 439-443.
• 9: KruskaI, C.P., Rudolph, L., and Snir, M. Efficient parallel algorithms for graph problems. In Proceedings of the IEEE 1986 International Conference on Parallel Processing, 1986, pp. 869-876.
• 10: Lawler, E.L. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, 1976.
• 11: James Orlin, A faster strongly polynomial minimum cost flow algorithm, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.377-387, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62249]
• 12: Peterson, G.L. A balanced tree scheme for meldable heaps with updates. Tech. Rep. GIT-ICS-87-23, School of Information and Comp. Sci., Georgia Institute of Technology, Atlanta, Ga., 1987.
• 13: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 14: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  E. Data

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Design, Theory