Theorem. [Fredman-Tarjan 1986] Starting from an empty Fibonacci heap,!
Fibonacci Heaps and Their Uses in Improved Network
Optimization Algorithms
MICHAEL L. FREDMAN
University of California, San Diego, L.a Jolla, California
AND
ROBERT ENDRE TARJAN
AT&T Bell Laboratories, Murray HilI, New Jersey
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 qlogn)
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:
( 1) O(n log n + m) for the single-source shortest path problem with nonnegative edge lengths, improved
from O(m logfmh+2)n);
(2) O(n*log n + nm) for the all-pairs shortest path problem, improved from O(nm lo&,,,+2,n);
(3) O(n*logn + nm) for the assignment problem (weighted bipartite matching), improved from
O(nm log0dn+2)n);
(4) O(mj3(m, n)) for the minimum spanning tree problem, improved from O(mloglo&,,.+2,n), where
j3(m, n) = min {i 1 log% 5 m/n). Note that B(m, n) 5 log*n if m 2 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.
Categories and Subject Descriptors: E.l [Data]: Data Structures--trees; graphs; F.2.2 [Analysis of
Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems-computations on
discrete structures; sorting and searching; G.2.2 [Discrete Mathematics]: Graph Theory-graph algo-
rithms; network problems; trees
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Heap, matching, minimum spanning tree, priority queue, shortest
Pati
’ A preliminary version of this paper appeared in the Proceedings of the 25th IEEE Symposium on the
Foundations of Computer Science (Singer Island, Fla., Oct. 24-26). IEEE, New York, 1984, pp. 338-
346, 0 IEEE. Any portion of this paper that appeared in the preliminary version is reprinted with
permission.
This research was supported in part by the National Science Foundation under grant MCS 82-0403 1.
Authors’ addresses: M. L. Fredman, Electrical Engineering and Computer Science Department, Uni-
versity of California, San Diego, La Jolla, CA 92093; R. E. Tarjan, AT&T Bell Laboratories, Murray
Hill, NJ 07974.
Permission to copy without fee all or part of this material is granted provided that the copies are not
made or distributed for direct commercial advantage, the ACM copyright notice and the title of the
publication and its date appear, and notice is given that copying is by permission of the Association for
Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.
0 1987 ACM 0004-541 l/87/0700-0596 $1.50
Journal ofthe Association for Computing Machinery, Vol. 34, No. 3, July 1987, Pages 596-615.
