AF-heap
Encyclopedia
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.
Using an AF-heap, it is possible to perform insert or decrease-key operations and delete-min operations on machine-integer keys in time . This allows Dijkstra's algorithm
to be performed in the same time bound on graphs with edges and vertices, and leads to a linear time algorithm for minimum spanning tree
s, with the assumption for both problems that the edge weights of the input graph are machine integers in the transdichotomous model
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the AF-heap is a type of priority queue
Priority queue
A priority queue is an abstract data type in computer programming.It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a "priority"....
for integer data, an extension of the fusion tree
Fusion tree
A fusion tree is a type of tree data structure in computer science. It implements an associative array with integer keys up to a fixed size; by exploiting the constant-time machine word multiplication operation available on many real processors, it is able to achieve all operations inO\lefttime ,...
using an atomic heap proposed by M. L. Fredman and D. E. Willard.
Using an AF-heap, it is possible to perform insert or decrease-key operations and delete-min operations on machine-integer keys in time . This allows Dijkstra's algorithm
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
to be performed in the same time bound on graphs with edges and vertices, and leads to a linear time algorithm for minimum spanning tree
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
s, with the assumption for both problems that the edge weights of the input graph are machine integers in the transdichotomous model
Transdichotomous model
In computational complexity theory, and more specifically in the analysis of algorithms with integer data, the transdichotomous model is a variation of the random access machine in which the machine word size is assumed to match the problem size. The model was proposed by Michael Fredman and Dan E...
.