Michael L. Fredman
Robert Endre Tarjan
Abstract
In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n-item heap in O(log n) amortized time and all other standard heap operations in O(1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms. In particular, we obtain the following worst-case bounds, where n is the number of vertices and m the number of edges in the problem graph:
O(n log n + m) for the single-source shortest path problem with nonnegative edge lengths, improved from O(mlog(m/n+2)n);
O(n2log n + nm) for the all-pairs shortest path problem, improved from O(nm log(m/n+2)n);
O(n2log n + nm) for the assignment problem (weighted bipartite matching), improved from O(nmlog(m/n+2)n);
O(mβ(m, n)) for the minimum spanning tree problem, improved from O(mlog log(m/n+2)n); where β(m, n) = min {i | log(i)n ≤ m/n}. Note that β(m, n) ≤ log*n if m ≥ n.
Of these results, the improved bound for minimum spanning trees is the most striking, although all the results give asymptotic improvements for graphs of appropriate densities.
- 1 AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass. 1974. Google Scholar
- 2 BROWN, M.R. Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7, 3 (Aug. 1978), 298-319.Google Scholar
- 3 CAMERINI, P. M., FRATTA, L., AND MAFFIOLI, F. A note on finding optimum branchings. Networks 9, 4 (Winter 1979), 309-312.Google Scholar
- 4 CHERITON, D., AND TARJAN, R.E. Finding minimum spanning trees. SIAM J. Comput. 5, 4 (Dec. 1976), 724-742.Google Scholar
- 5 DIJKSTRA, E.W. A note on two problems in connexion with graphs. Numer. Math. 1, 4 (Sept. 1959), 269-27 i.Google Scholar
- 6 EDMONDS, J., AND KARP, R.M. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 2 (Apr. 1972), 248-264. Google Scholar
- 7 GABOW, H. N., AND STALLMAN, M. Efficient algorithms for the parity and intersection problems on graphic matroids. In Automata, Languages, and Programming, 12th Colloquium, Lecture Notes in Computer Science, Vol. 194, W. Brauer, Ed. Springer-Vedag, New York, 1985, pp. 210-220. Google Scholar
- 8 GABOW, H. N., AND TARJAN, R. E. Efficient algorithms for a family of matroid intersection problems. J. Algorithms 5, 1 (Mar. 1984), 80-131.Google Scholar
- 9 GABOW, H. N., GALIL, Z., AND SPENCER, T. Efficient implementation of graph algorithms using contraction. In Proceedings of the 25th Annual IEEE Symposium on Foundations of Computing. (Singer Island, Fla., Oct. 24-26). }EEL Press, New York, 1984 pp. 338-346.Google Scholar
- 10 GABOW, H. N., GALIL, Z., SPENCER, T., AND TARJAN, R. E. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6, 2 (1986), 109-122. Google Scholar
- 11 GRAHAM, R. L., AND HELL, P. On the history of the minimum spanning tree problem. Ann. Hist. Comput. 7, I (Jan. 1985), 43-57.Google Scholar
- 12 JARNIK, V. O jist6m probl6mu minimalnim. Prdca Moravskb PT'irodovbdeckb Spoleknosti 6 (1930), 57-63 (in Czechoslovakian).Google Scholar
- 13 JOHNSON, D. B. Efficient algorithms for shortest paths in sparse networks. J. ACM 24, l (Jan. 1977), 1-13. Google Scholar
- 14 KNUTH, D.E. The Art of Computer Programming. Vol. 1, Fundamental Algorithms, 2nd ed. Addison-Wesley, Reading, Mass. 1973. Google Scholar
- 15 KNtrrH, D.E. The Art of Computer Programming. Vol. 3, Sorting and Searching. Addison- Wesley, Reading, Mass., 1973.Google Scholar
- 16 KNUTH, D.E. A generalization of Dijkstra's algorithm. Inf. Process. Lett. 6, 1 (Feb. 1977), 1-5.Google Scholar
- 17 KOMLOS, J. Linear verification for spanning trees. In Proceedings of the 25th Annual IEEE Symposium on Foundations of Computing. (Singer Island, Fla., Oct. 24-26). IEEE Press, New York, 1984 pp. 201-206.Google Scholar
- 18 PRIM, R.C. Shortest connection networks and some generalizations. Bell Syst. Tech. ~ 36, 6 (Nov. 1957), 1389-1401.Google Scholar
- 19 SLEATOR, D. O., AND TARJAN, R.E. Self-adjusting heaps. SIAM J. Comput. 15, 1 (Feb. 1986), 52-69. Google Scholar
- 20 SUURBALLE, J. W., AND TARJAN, R. E. A quick method for finding shortest pairs of paths. Networks 14 (1984), 325-336.Google Scholar
- 21 TAIUAN, R.E. Finding optimum branchings. Networks 7, 1 (Spring 1977), 25-35.Google Scholar
- 22 TARJAN, R. E. A class of algorithms which require nonlinear time to maintain disjoint sets. I. Comput. Syst. Sci. 18, 2 (Apr. 1979), 110-127.Google Scholar
- 23 TARJAN, R.E. Applications of path compression on balanced trees. J. ACM 26, 4 (Oct. 1979), 690-715. ~ Google Scholar
- 24 TARJAN, R. E. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1983. Google Scholar
- 25 TARJAN, R.E. Amortized computational complexity. SIAM J. Algebraic Discrete Methods 6, 2 (Apr. 1985), 306-318.Google Scholar
- 26 TAgJAN, R. E., AND VAN L~EUWEN, J. Worst-case analysis of set union algorithms. J. ACM 31, 2 (I 984), 245-28 i. Google Scholar
- 27 VUILLEMIN, J. A data structure for manipulating priority queues. Commun. ACM 21, 4 (Apr. 1978), 309-315. Google Scholar
- 28 YAO, A. An O(IEI log log I V I) algorithm for finding minimum spanning trees. Inf. Process, Lett. 4, I (Sept. 1975), 21-23.Google Scholar
Index Terms
- Fibonacci heaps and their uses in improved network optimization algorithms
Recommendations
Strict fibonacci heaps
STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computingWe present the first pointer-based heap implementation with time bounds matching those of Fibonacci heaps in the worst case. We support make-heap, insert, find-min, meld and decrease-key in worst-case O(1) time, and delete and delete-min in worst-case O(...
Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation
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 ...
Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms
SFCS '84: Proceedings of the 25th Annual Symposium onFoundations of Computer Science, 1984In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary ...
Reviews
Hausi Albert Muller
The authors of this paper define a collection of new data structures called Fibonacci heaps or F-heaps for implementing heaps or priority queues. F-heaps support the delete and delete min operations in O(log n) amortized time and all other standard heap operations in O(1) amortized time (i.e., make heap, insert, find min, meld, decrease key). As stated in the paper's abstract, F-heaps are a direct extension of binomial queues, which support all the heap operations in O(log n) worst-case time. A Fibonacci heap is a set of item-disjoint heap-ordered trees (i.e., the root node contains the minimum key, and the key of any other node is no less than the key of its parent). The structure of the tree is defined by the operations performed on the tree: a node with k children has at least F k+2 descendants including itself, where F 1=1; F 2=1; F k= F k-1+ F k-2; thus, the minimum number of nodes of a tree in an F-heap is a Fibonacci number, hence, the name Fibonacci heaps. Dijkstra uses a similar type of trees, Leonardo trees ( L 1=1; L 2=1; L k= L k?1+ L:- 0Ik?2+1) in his Smoothsort algorithm [1], which is based on Williams's Heapsort algorithm; however, Smoothsort or Leonardo trees are not mentioned in the paper. The paper shows how Fibonacci heaps can be used to obtain improved running times for network optimization algorithms such as Dijkstra's shortest paths and Prim's minimum spanning tree. The new worst-case bounds for graphs of intermediate density ( n:3WiCm:3WiCm 2) are listed in the following table, where n is the number of vertices, m is the number of edges, and &bgr;( m, n)=min{ i &vbm0; log ( i) n?Cm- / n}. :.OC :.HB Single-source shortest path All-pairs shortest path Weighted bipartite matching Minimum spanning tree :.HS :.HS O( n log n+ m) O( n 2 log n+ nm) O( n 2 log n+ nm) O( m &bgr;( m,n)) :.HT :.OE The paper concludes by stating three open problems raised by this research and by listing additional applications of Fibonacci heaps that were explored recently by Gabow, Galil, and Spencer [2]. :.OC :.HB Minimum spanning tree Shortest pair of disjoint paths Optimum branching :.HS :.HS O( m log &bgr;( m,n)) O( n log n+ m) O( n log n+ m) :.HT :.OE F-heaps could be presented in any computer science course discussing algorithms and data structures. The material presented in this well-written paper will certainly find its way into textbooks. Fibonacci heaps are an outstanding research contribution in the area of network optimization algorithms and data structures.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments