In computer science, a
Contents 1 Structure 2 Implementation of operations 3 Proof of degree bounds 4 Worst case 5 Summary of running times 6 Practical considerations 7 References 8 External links Structure[edit] Figure 1. Example of a Fibonacci heap. It has three trees of degrees 0, 1 and 3. Three vertices are marked (shown in blue). Therefore, the potential of the heap is 9 (3 trees + 2 × (3 marked-vertices)). A
Potential = t + 2m where t is the number of trees in the Fibonacci heap, and m is the number of marked nodes. 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). The amortized time for an operation is given by the sum of the actual time and c times the difference in potential, where c is a constant (chosen to match the constant factors in the O notation for the actual time). Thus, the root of each tree in a heap has one unit of time stored. This unit of time can be used later to link this tree with another tree at amortized time 0. Also, each marked node has two units of time stored. One can be used to cut the node from its parent. If this happens, the node becomes a root and the second unit of time will remain stored in it as in any other root. Implementation of operations[edit] 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 whether the node is marked. Moreover, we maintain a pointer to the root containing the minimum key. Operation find minimum is now trivial because we keep the pointer to the node containing it. It does not change the potential of the heap, therefore both actual and amortized cost are constant. As mentioned above, merge is implemented simply by concatenating the lists of tree roots of the two heaps. This can be done in constant time and the potential does not change, leading again to constant amortized time. Operation insert works by creating a new heap with one element and doing merge. This takes constant time, and the potential increases by one, because the number of trees increases. The amortized cost is thus still constant. Operation extract minimum (same as delete minimum) operates in three phases. First we take the root containing the minimum element and remove it. Its children will become roots of new trees. If the number of children was d, it takes time O(d) to process all new roots and the potential increases by d−1. Therefore, the amortized running time of this phase is O(d) = O(log n). However to complete the extract minimum operation, we need to update the pointer to the root with minimum key. Unfortunately there may be up to n roots we need to check. In the second phase we therefore decrease the number of roots by successively linking together roots of the same degree. When two roots u and v have the same degree, we make one of them a child of the other so that the one with the smaller key remains the root. Its degree will increase by one. This is repeated until every root has a different degree. To find trees of the same degree efficiently we use an array of length O(log n) in which we keep a pointer to one root of each degree. When a second root is found of the same degree, the two are linked and the array is updated. The actual running time is O(log n + m) where m is the number of roots at the beginning of the second phase. At the end we will have at most O(log n) roots (because each has a different degree). Therefore, the difference in the potential function from before this phase to after it is: O(log n) − m, and the amortized running time is then at most O(log n + m) + c(O(log n) − m). With a sufficiently large choice of c, this simplifies to O(log n). Figure 2.
Figure 3.
Figure 4.
In the third phase we check each of the remaining roots and find the
minimum. This takes O(log n) time and the potential does not change.
The overall amortized running time of extract minimum is therefore
O(log n).
Operation decrease key will take the node, decrease the key and if the
heap property becomes violated (the new key is smaller than the key of
the parent), the node is cut from its parent. If the parent is not a
root, it is marked. If it has been marked already, it is cut as well
and its parent is marked. We continue upwards until we reach either
the root or an unmarked node. Now we set the minimum pointer to the
decreased value if it is the new minimum. In the process we create
some number, say k, of new trees. Each of these new trees except
possibly the first one was marked originally but as a root it will
become unmarked. One node can become marked. Therefore, the number of
marked nodes changes by
−(k − 1) + 1 = − k + 2.
Combining these 2 changes, the potential changes by
2(−k + 2) + k = −k + 4.
The actual time to perform the cutting was O(k), therefore (again with
a sufficiently large choice of c) the amortized running time is
constant.
Finally, operation delete can be implemented simply by decreasing the
key of the element to be deleted to minus infinity, thus turning it
into the minimum of the whole heap. Then we call extract minimum to
remove it. The amortized running time of this operation is O(log n).
Proof of degree bounds[edit]
The amortized performance of a
F d + 2 ≥ φ d displaystyle F_ d+2 geq varphi ^ d for all integers d ≥ 0 displaystyle dgeq 0 , where φ = ( 1 + 5 ) / 2 ≐ 1.618 displaystyle varphi =(1+ sqrt 5 )/2doteq 1.618 . (We then have n ≥ F d + 2 ≥ φ d displaystyle ngeq F_ d+2 geq varphi ^ d , and taking the log to base φ displaystyle varphi of both sides gives d ≤ log φ n displaystyle dleq log _ varphi n as required.) Consider any node x somewhere in the heap (x need not be the root of one of the main trees). Define size(x) to be the size of the tree rooted at x (the number of descendants of x, including x itself). We prove by induction on the height of x (the length of a longest simple path from x to a descendant leaf), that size(x) ≥ Fd+2, where d is the degree of x. Base case: If x has height 0, then d = 0, and size(x) = 1 = F2. Inductive case: Suppose x has positive height and degree d>0. Let y1, y2, ..., yd be the children of x, indexed in order of the times they were most recently made children of x (y1 being the earliest and yd the latest), and let c1, c2, ..., cd be their respective degrees. We claim that ci ≥ i-2 for each i with 2≤i≤d: Just before yi was made a child of x, y1,...,yi−1 were already children of x, and so x had degree at least i−1 at that time. Since trees are combined only when the degrees of their roots are equal, it must have been that yi also had degree at least i-1 at the time it became a child of x. From that time to the present, yi can only have lost at most one child (as guaranteed by the marking process), and so its current degree ci is at least i−2. This proves the claim. Since the heights of all the yi are strictly less than that of x, we can apply the inductive hypothesis to them to get size(yi) ≥ Fci+2 ≥ F(i−2)+2 = Fi. The nodes x and y1 each contribute at least 1 to size(x), and so we have size ( x ) ≥ 2 + ∑ i = 2 d size ( y i ) ≥ 2 + ∑ i = 2 d F i = 1 + ∑ i = 0 d F i . displaystyle textbf size (x)geq 2+sum _ i=2 ^ d textbf size (y_ i )geq 2+sum _ i=2 ^ d F_ i =1+sum _ i=0 ^ d F_ i . A routine induction proves that 1 + ∑ i = 0 d F i = F d + 2 displaystyle 1+sum _ i=0 ^ d F_ i =F_ d+2 for any d ≥ 0 displaystyle dgeq 0 , which gives the desired lower bound on size(x).
Worst case[edit]
Although Fibonacci heaps look very efficient, they have the following
two drawbacks (as mentioned in the paper "The Pairing Heap: A new form
of Self Adjusting Heap"): "They are complicated when it comes to
coding them. Also they are not as efficient in practice when compared
with the theoretically less efficient forms of heaps, since in their
simplest version they require storage and manipulation of four
pointers per node, compared to the two or three pointers per node
needed for other structures ".[3] These other structures are referred
to Binary heap, Binomial heap, Pairing Heap, Brodal Heap and Rank
Pairing Heap.
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 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. It is
possible to create a data structure which has the same worst-case
performance as the
Operation Binary[6] Leftist Binomial[6] Fibonacci[6][2] Pairing[7] Brodal[8][a] Rank-pairing[10] Strict Fibonacci[11] find-min Θ(1) Θ(1) Θ(log n) Θ(1) Θ(1) Θ(1) Θ(1) Θ(1) delete-min Θ(log n) Θ(log n) Θ(log n) O(log n)[b] O(log n)[b] O(log n) O(log n)[b] O(log n) insert O(log n) Θ(log n) Θ(1)[b] Θ(1) Θ(1) Θ(1) Θ(1) Θ(1) decrease-key Θ(log n) Θ(n) Θ(log n) Θ(1)[b] o(log n)[b][c] Θ(1) Θ(1)[b] Θ(1) merge Θ(n) Θ(log n) O(log n)[d] Θ(1) Θ(1) Θ(1) Θ(1) Θ(1) ^ Brodal and Okasaki later describe a persistent variant with the same bounds except for decrease-key, which is not supported. Heaps with n elements can be constructed bottom-up in O(n).[9] ^ a b c d e f g Amortized time. ^ Lower bound of Ω ( log log n ) , displaystyle Omega (log log n), [12] upper bound of O ( 2 2 log log n ) . displaystyle O(2^ 2 sqrt log log n ). [13] ^ n is the size of the larger heap. Practical considerations[edit] This section needs expansion. You can help by adding to it. (February 2015) Fibonacci heaps have a reputation for being slow in practice[14] due to large memory consumption per node and high constant factors on all operations.[15] Recent experimental results suggest that Fibonacci heaps are more efficient in practice than most of its later derivatives, including quake heaps, violation heaps, strict Fibonacci heaps, rank pairing heaps, but less efficient than either pairing heaps or array-based heaps.[16] References[edit] ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein,
Clifford (2001) [1990]. "Chapter 20: Fibonacci Heaps". Introduction to
Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 476–497.
ISBN 0-262-03293-7. Third edition p. 518.
^ a b c Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987).
"Fibonacci heaps and their uses in improved network optimization
algorithms" (PDF). Journal of the Association for Computing Machinery.
34 (3): 596–615. doi:10.1145/28869.28874.
^ Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan,
Robert E. (1986). "The pairing heap: a new form of self-adjusting
heap" (PDF). Algorithmica. 1 (1): 111–129.
doi:10.1007/BF01840439.
^ Gerth Stølting Brodal (1996), "Worst-Case Efficient Priority
Queues", Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, Society
for Industrial and Applied Mathematics: 52–58,
CiteSeerX 10.1.1.43.8133 , doi:10.1145/313852.313883,
ISBN 0-89871-366-8
^ Brodal, G. S. L.; Lagogiannis, G.; Tarjan, R. E. (2012). Strict
Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of
Computing - STOC '12. p. 1177. doi:10.1145/2213977.2214082.
ISBN 978-1-4503-1245-5.
^ a b c d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.
(1990).
External links[edit] Java applet simulation of a Fibonacci heap
MATLAB implementation of Fibonacci heap
De-recursived and memory efficient C implementation of Fibonacci heap
(free/libre software, CeCILL-B license)
Ruby implementation of the
v t e Data structures Types Collection Container Abstract Associative array Multimap List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set Arrays Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix Linked Association list Linked list Skip list Unrolled linked list XOR linked list Trees B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree Graphs Binary decision diagram Directed acyclic graph Directed acyclic word graph List of dat |