AF-heap
In computer science, the AF-heap is a type of priority queue for integer data, an extension of the fusion tree using an proposed by M. L. Fredman and D. E. Willard.[1]
Using an AF-heap, it is possible to perform m insert or decrease-key operations and n delete-min operations on machine-integer keys in time O(m + n log n / log log n). This allows Dijkstra's algorithm to be performed in the same O(m + n log n / log log n) time bound on graphs with n edges and m vertices, and leads to a linear time algorithm for minimum spanning trees, with the assumption for both problems that the edge weights of the input graph are machine integers in the transdichotomous model.
See also[]
References[]
- ^ M. L. Fredman and D. E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. Journal of Computer and System Sciences 48, 533-551 (1994)
Categories:
- Heaps (data structures)
- Priority queues
- Algorithms and data structures stubs
- Combinatorics stubs