Fibonacci heap
In computer science, a Fibonacci heap is a data structure similar to a binomial heap but with a better amortized running time. A Fibonacci heap can be used to improve the running time of Dijkstra's algorithm for computing shortest paths in a graph and Prim's algorithm for computing a minimum spanning tree of a graph.In particular, operations insert, find minimum, decrease key, and union work in constant amortized time. Operations delete and delete minimum work in O(log n) amortized time. This means that any sequence of a operations from the first group and b operations from the second group would take O(a+b log a) time. In a binomial heap such a sequence of operations would take O((a+b)log (a)) time. A Fibonacci heap is thus better than a binomial heap when the number of b is asymptotically smaller than a.
Although the total running time of a sequence of operations starting with an empty structure is bounded by the bounds given above, some (very few) operations in the sequence can take very long to complete (in particular decrease key, delete and delete minimum have linear running time in the worst case). For this reason Fibonacci heaps and other amortized data structures may not be appropriate for real-time systems.
| Table of contents |
|
2 External links 3 References |
A Fibonacci heap is a collection of treess satisfying the minimum-heap property, that is, the key of a child is always greater than or equal to the key of the parent. This implies that the minimum key is always at the root of one of the trees. Compared with binomial heaps, the structure of a Fibonacci heap is more flexible. The number of trees in a heap can be as high as n (i.e. each element would be in a separate tree) and the trees do not have a prescribed shape. However, a subtree rooted in any node has size exponential in the number of children of that node, which implies that each node has at most O(log n) children.
Structure of a Fibonacci heap
To allow fast deletion and concatenation, the roots of all trees are linked using a circular, doubly linked list. The children of each node are also linked using such a list. For each node, we maintain its number of children and a special mark. A node is marked if
at least one of its children was cut since this node was made a child of another node (all roots are unmarked).
Moreover we maintain a pointer to the root containing the minimum key.
The potential function in the amortized analysis of a Fibonacci heap is given by
- Potential = t + 2m
External links
References