Английская Википедия: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 atomic heap proposed by M. L. Fredman and D. E. Willard.[1]
Using an AF-heap, it is possible to perform Шаблон:Mvar insert or decrease-key operations and Шаблон:Mvar delete-min operations on machine-integer keys in time Шаблон:Math. This allows Dijkstra's algorithm to be performed in the same Шаблон:Math time bound on graphs with Шаблон:Mvar edges and Шаблон:Mvar 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)
Шаблон:Algorithm-stub Шаблон:Combin-stub
