## 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(n^{2}log n + nm) for the all-pairs shortest path problem, improved from O(nm log_{(m/n+2)}n); O(n^{2}log 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.

Original language | English (US) |
---|---|

Pages (from-to) | 596-615 |

Number of pages | 20 |

Journal | Journal of the ACM (JACM) |

Volume | 34 |

Issue number | 3 |

DOIs | |

State | Published - Jul 1 1987 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence