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)|
|Number of pages||9|
|State||Published - Dec 1 1984|
|Name||Annual Symposium on Foundations of Computer Science (Proceedings)|
All Science Journal Classification (ASJC) codes
- Hardware and Architecture