### Abstract

A new data structure for implementing heaps (priority queues) is developed. The structure, Fibonacci heaps (F-heaps), extends the binomial queues proposed by J. Vuillemin (1978). F-heaps support arbitrary deletion from an n-item heap in O(log n) amortized time and all other standard heap operations in O(l) amortized time. Using F-heaps, one can obtain improved running times for several network optimization algorithms.

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

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | IEEE |

Pages | 338-346 |

Number of pages | 9 |

ISBN (Print) | 081860591X |

State | Published - Dec 1 1984 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### All Science Journal Classification (ASJC) codes

- Hardware and Architecture

## Fingerprint Dive into the research topics of 'FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS.'. Together they form a unique fingerprint.

## Cite this

Fredman, M. L., & Tarjan, R. E. (1984). FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS. In

*Annual Symposium on Foundations of Computer Science (Proceedings)*(pp. 338-346). (Annual Symposium on Foundations of Computer Science (Proceedings)). IEEE.