TY - GEN
T1 - FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS.
AU - Fredman, Michael L.
AU - Tarjan, Robert Endre
PY - 1984
Y1 - 1984
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0021551631&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0021551631&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0021551631
SN - 081860591X
T3 - Annual Symposium on Foundations of Computer Science (Proceedings)
SP - 338
EP - 346
BT - Annual Symposium on Foundations of Computer Science (Proceedings)
PB - IEEE
ER -