Fibonacci heap

Last updated
Fibonacci heap
Type heap
Invented1984
Invented byMichael L. Fredman and Robert E. Tarjan
Complexities in big O notation
Space complexity
Time complexity
Function Amortized Worst Case
InsertΘ(1)
Find-minΘ(1)
Delete-min O(log n)
Decrease-keyΘ(1)
MergeΘ(1)

In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binary heap and binomial heap. Michael L. Fredman and Robert E. Tarjan developed Fibonacci heaps in 1984 and published them in a scientific journal in 1987. Fibonacci heaps are named after the Fibonacci numbers, which are used in their running time analysis.

Contents

The amortized times of all operations on Fibonacci heaps is constant, except delete-min. [1] [2] Deleting an element (most often used in the special case of deleting the minimum element) works in amortized time, where is the size of the heap. [2] This means that starting from an empty data structure, any sequence of a insert and decrease-key operations and bdelete-min operations would take worst case time, where is the maximum heap size. In a binary or binomial heap, such a sequence of operations would take time. A Fibonacci heap is thus better than a binary or binomial heap when is smaller than by a non-constant factor. It is also possible to merge two Fibonacci heaps in constant amortized time, improving on the logarithmic merge time of a binomial heap, and improving on binary heaps which cannot handle merges efficiently.

Using Fibonacci heaps improves the asymptotic running time of algorithms which utilize priority queues. For example, Dijkstra's algorithm and Prim's algorithm can be made to run in time.

Structure

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 x (3 marked-vertices)). Fibonacci heap.png
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 Fibonacci heap is a collection of trees 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 trees do not have a prescribed shape and in the extreme case the heap can have every element in a separate tree. This flexibility allows some operations to be executed in a lazy manner, postponing the work for later operations. For example, merging heaps is done simply by concatenating the two lists of trees, and operation decrease key sometimes cuts a node from its parent and forms a new tree.

However, at some point order needs to be introduced to the heap to achieve the desired running time. In particular, degrees of nodes (here degree means the number of direct children) are kept quite low: every node has degree at most and the size of a subtree rooted in a node of degree is at least , where is the th Fibonacci number. This is achieved by the rule: at most one child can be cut off each non-root node. When a second child is cut, the node itself needs to be cut from its parent and becomes the root of a new tree (see Proof of degree bounds, below). The number of trees is decreased in the operation delete-min, where trees are linked together.

As a result of a relaxed structure, some operations can take a long time while others are done very quickly. For the amortized running time analysis, we use the potential method, in that we pretend that very fast operations take a little bit longer than they actually do. This additional time is then later combined and subtracted from the actual running time of slow operations. The amount of time saved for later use is measured at any given moment by a potential function. The potential of a Fibonacci heap is given by

,

where is the number of trees in the Fibonacci heap, and 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 times the difference in potential, where c is a constant (chosen to match the constant factors in the big 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.

Operations

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.

Find-min

We maintain a pointer to the root containing the minimum key, allowing access to the minimum. This pointer must be updated during the other operations, which adds only a constant time overhead.

Merge

The merge operation simply concatenates the root lists of two heaps together, and setting the minimum to be the smaller of the two heaps. This can be done in constant time, and the potential does not change, leading again to constant amortized time.

Insert

The insertion operation can be considered a special case of the merge operation, with a single node. The node is simply appended to the root list, increasing the potential by one. The amortized cost is thus still constant.

Delete-min

Figure 2. First phase of delete-min. Fibonacci heap extractmin1.png
Figure 2. First phase of delete-min.
Figure 3. Third phase of delete-min. Fibonacci heap extractmin2.png
Figure 3. Third phase of delete-min.

The delete-min operation does most of the work in restoring the structure of the heap. It has three phases:

  1. The root containing the minimum element is removed, and each of its children becomes a new root. It takes time to process these new roots, and the potential increases by . Therefore, the amortized running time of this phase is .
  2. There may be up to roots. We therefore decrease the number of roots by successively linking together roots of the same degree. When two roots have the same degree, we make the one with the larger key a child of the other, so that the minimum heap property is observed. The degree of the smaller root increases 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 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 , where is the number of roots at the beginning of the second phase. In the end, we will have at most roots (because each has a different degree). Therefore, the difference in the potential from before to after this phase is . Thus, the amortized running time is . By choosing a sufficiently large such that the terms in cancel out, this simplifies to .
  3. Search the final list of roots to find the minimum, and update the minimum pointer accordingly. This takes time, because the number of roots has been reduced.

Overall, the amortized time of this operation is , provided that . The proof of this is given in the following section.

Decrease-key

Figure 4. Fibonacci heap from Figure 1 after decreasing key of node 9 to 0. Fibonacci heap-decreasekey.png
Figure 4. Fibonacci heap from Figure 1 after decreasing key of node 9 to 0.

If decreasing the key of a node causes it to become smaller than its parent, then it is cut from its parent, becoming a new unmarked root. If it is also less than the minimum key, then the minimum pointer is updated.

We then initiate a series of cascading cuts, starting with the parent of . As long as the current node is marked, it is cut from its parent and made an unmarked root. Its original parent is then considered. This process stops when we reach an unmarked node . If is not a root, it is marked. In this process we introduce some number, say , of new trees. Except possibly , each of these new trees loses its original mark. The terminating node may become marked. Therefore, the change in the number of marked nodes is between of and . The resulting change in potential is . The actual time required to perform the cutting was . Hence, the amortized time is , which is constant, provided is sufficiently large.

Proof of degree bounds

The amortized performance of a Fibonacci heap depends on the degree (number of children) of any tree root being , where is the size of the heap. Here we show that the size of the (sub)tree rooted at any node of degree in the heap must have size at least , where is the th Fibonacci number. The degree bound follows from this and the fact (easily proved by induction) that for all integers , where is the golden ratio. We then have , and taking the log to base of both sides gives as required.

Let be an arbitrary node in a Fibonacci heap, not necessarily a root. Define to be the size of the tree rooted at (the number of descendants of , including itself). We prove by induction on the height of (the length of the longest path from to a descendant leaf) that , where is the degree of .

Base case: If has height , then , and .

Inductive case: Suppose has positive height and degree . Let be the children of , indexed in order of the times they were most recently made children of ( being the earliest and the latest), and let be their respective degrees.

We claim that for each . Just before was made a child of , were already children of , and so must have had degree at least at that time. Since trees are combined only when the degrees of their roots are equal, it must have been the case that also had degree at least at the time when it became a child of . From that time to the present, could have only lost at most one child (as guaranteed by the marking process), and so its current degree is at least . This proves the claim.

Since the heights of all the are strictly less than that of , we can apply the inductive hypothesis to them to get

The nodes and each contribute at least 1 to , and so we have

where the last step is an identity for Fibonacci numbers. This gives the desired lower bound on .

Performance

Although Fibonacci heaps look very efficient, they have the following two drawbacks: [3]

  1. They are complicated to implement.
  2. They are not as efficient in practice when compared with theoretically less efficient forms of heaps. [4] In their simplest version, they require manipulation of four pointers per node, whereas only two or three pointers per node are needed in other structures, such as the binomial heap, or pairing heap. This results in large memory consumption per node and high constant factors on all operations.

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-min has 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 Fibonacci heap has amortized performance. One such structure, the Brodal queue, [5] is, in the words of the creator, "quite complicated" and "[not] applicable in practice." Invented in 2012, the strict Fibonacci heap [6] is a simpler (compared to Brodal's) structure with the same worst-case bounds. Despite being simpler, experiments show that in practice the strict Fibonacci heap performs slower than more complicated Brodal queue and also slower than basic Fibonacci heap. [7] [8] The run-relaxed heaps of Driscoll et al. give good worst-case performance for all Fibonacci heap operations except merge. [9] Recent experimental results suggest that the Fibonacci heap is more efficient in practice than most of its later derivatives, including quake heaps, violation heaps, strict Fibonacci heaps, and rank pairing heaps, but less efficient than pairing heaps or array-based heaps. [8]

Summary of running times

Here are time complexities [10] of various heap data structures. Function names assume a min-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.

Operationfind-mindelete-mininsertdecrease-keymeld
Binary [10] Θ(1)Θ(log n)O(log n)O(log n)Θ(n)
Leftist Θ(1)Θ(log n)Θ(log n)O(log n)Θ(log n)
Binomial [10] [11] Θ(1)Θ(log n)Θ(1) [lower-alpha 1] Θ(log n)O(log n)
Skew binomial [12] Θ(1)Θ(log n)Θ(1)Θ(log n)O(log n) [lower-alpha 2]
Pairing [13] Θ(1)O(log n) [lower-alpha 1] Θ(1)o(log n) [lower-alpha 1] [lower-alpha 3] Θ(1)
Rank-pairing [16] Θ(1)O(log n) [lower-alpha 1] Θ(1)Θ(1) [lower-alpha 1] Θ(1)
Fibonacci [10] [2] Θ(1)O(log n) [lower-alpha 1] Θ(1)Θ(1) [lower-alpha 1] Θ(1)
Strict Fibonacci [17] Θ(1)O(log n)Θ(1)Θ(1)Θ(1)
Brodal [18] [lower-alpha 4] Θ(1)O(log n)Θ(1)Θ(1)Θ(1)
2–3 heap [20] Θ(1)O(log n) [lower-alpha 1] Θ(1) [lower-alpha 1] Θ(1)O(log n)
  1. 1 2 3 4 5 6 7 8 9 Amortized time.
  2. Brodal and Okasaki describe a technique to reduce the worst-case complexity of meld to Θ(1); this technique applies to any heap datastructure that has insert in Θ(1) and find-min, delete-min, meld in O(log n).
  3. Lower bound of [14] upper bound of [15]
  4. 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). [19]

Related Research Articles

<span class="mw-page-title-main">AVL tree</span> Self-balancing binary search tree

In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

<span class="mw-page-title-main">Heap (data structure)</span> Computer science data structure

In computer science, a heap is a tree-based data structure that satisfies the heap property: In a max heap, for any given node C, if P is a parent node of C, then the key of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap is called the root node.

In computer science, a priority queue is an abstract data type similar to a regular queue or stack abstract data type. Each element in a priority queue has an associated priority. In a priority queue, elements with high priority are served before elements with low priority. In some implementations, if two elements have the same priority, they are served in the same order in which they were enqueued. In other implementations, the order of elements with the same priority is undefined.

A splay tree is a binary search tree with the additional property that recently accessed elements are quick to access again. Like self-balancing binary search trees, a splay tree performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For random access patterns drawn from a non-uniform random distribution, their amortized time can be faster than logarithmic, proportional to the entropy of the access pattern. For many patterns of non-random operations, also, splay trees can take better than logarithmic time, without requiring advance knowledge of the pattern. According to the unproven dynamic optimality conjecture, their performance on all access patterns is within a constant factor of the best possible performance that could be achieved by any other self-adjusting binary search tree, even one selected to fit that pattern. The splay tree was invented by Daniel Sleator and Robert Tarjan in 1985.

<span class="mw-page-title-main">Dijkstra's algorithm</span> Algorithm for finding shortest paths

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

<span class="mw-page-title-main">Prim's algorithm</span> Method for finding minimum spanning trees

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

<span class="mw-page-title-main">Binary heap</span> Variant of heap data structure

A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.

In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap, as it supports merging two heaps in logarithmic time. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin.

In computer science, a 2–3 heap is a data structure, a variation on the heap, designed by Tadao Takaoka in 1999. The structure is similar to the Fibonacci heap, and borrows from the 2–3 tree.

In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets, and finding a representative member of a set. The last operation makes it possible to find out efficiently if any two elements are in the same or different sets.

In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an s-value which is the distance to the nearest leaf in subtree rooted at x. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the heap property, leftist trees are maintained so the right descendant of each node has the lower s-value.

A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986. Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a "robust choice" for implementing such algorithms as Prim's MST algorithm, and support the following operations :

A link/cut tree is a data structure for representing a forest, a set of rooted trees, and offers the following operations:

The d-ary heap or d-heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2. Thus, a binary heap is a 2-heap, and a ternary heap is a 3-heap. According to Tarjan and Jensen et al., d-ary heaps were invented by Donald B. Johnson in 1975.

In computer science, a skew binomial heap is a data structure for priority queue operations. It is a variant of the binomial heap that supports constant-time insertion operations in the worst case, rather than amortized time.

In computer science, the Brodal queue is a heap/priority queue structure with very low worst case time bounds: for insertion, find-minimum, meld and decrease-key and for delete-minimum and general deletion. They are the first heap variant to achieve these bounds without resorting to amortization of operational costs. Brodal queues are named after their inventor Gerth Stølting Brodal.

<span class="mw-page-title-main">Kinetic heap</span>

A Kinetic Heap is a kinetic data structure, obtained by the kinetization of a heap. It is designed to store elements where the priority is changing as a continuous function of time. As a type of kinetic priority queue, it maintains the maximum priority element stored in it. The kinetic heap data structure works by storing the elements as a tree that satisfies the following heap property – if B is a child node of A, then the priority of the element in A must be higher than the priority of the element in B. This heap property is enforced using certificates along every edge so, like other kinetic data structures, a kinetic heap also contains a priority queue to maintain certificate failure times.

In computer science, the list-labeling problem involves maintaining a totally ordered set S supporting the following operations:

This is a comparison of the performance of notable data structures, as measured by the complexity of their logical operations. For a more comprehensive listing of data structures, see List of data structures.

In computer science, a strict Fibonacci heap is a priority queue data structure with low worst case time bounds. It matches the amortized time bounds of the Fibonacci heap in the worst case. To achieve these time bounds, strict Fibonacci heaps maintain several invariants by performing restoring transformations after every operation. These transformations can be done in constant time by using auxiliary data structures to track invariant violations, and the pigeonhole principle guarantees that these can be fixed. Strict Fibonacci heaps were invented in 2012 by Gerth S. Brodal, George Lagogiannis, and Robert E. Tarjan.

References

  1. 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.
  2. 1 2 3 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. CiteSeerX   10.1.1.309.8927 . doi:10.1145/28869.28874.
  3. 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–4): 111–129. doi:10.1007/BF01840439. S2CID   23664143.
  4. http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf, p. 79
  5. 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 , ISBN   0-89871-366-8
  6. 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.
  7. Mrena, Michal; Sedlacek, Peter; Kvassay, Miroslav (June 2019). "Practical Applicability of Advanced Implementations of Priority Queues in Finding Shortest Paths". 2019 International Conference on Information and Digital Technologies (IDT). Zilina, Slovakia: IEEE. pp. 335–344. doi:10.1109/DT.2019.8813457. ISBN   9781728114019. S2CID   201812705.
  8. 1 2 Larkin, Daniel; Sen, Siddhartha; Tarjan, Robert (2014). "A Back-to-Basics Empirical Study of Priority Queues". Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments: 61–72. arXiv: 1403.0252 . Bibcode:2014arXiv1403.0252L. doi:10.1137/1.9781611973198.7. ISBN   978-1-61197-319-8. S2CID   15216766.
  9. Driscoll, James R.; Gabow, Harold N.; Shrairman, Ruth; Tarjan, Robert E. (November 1988). "Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation". Communications of the ACM. 31 (11): 1343–1354. doi: 10.1145/50087.50096 . S2CID   16078067.
  10. 1 2 3 4 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN   0-262-03141-8.
  11. "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-09-30.
  12. Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Optimal purely functional priority queues", Journal of Functional Programming, 6 (6): 839–857, doi: 10.1017/s095679680000201x
  13. Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv: 1110.4428 , CiteSeerX   10.1.1.748.7812 , doi:10.1007/3-540-44985-X_5, ISBN   3-540-67690-2
  14. Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery . 46 (4): 473–501. doi:10.1145/320211.320214.
  15. Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX   10.1.1.549.471 . doi:10.1109/SFCS.2005.75. ISBN   0-7695-2468-0.
  16. Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
  17. Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX   10.1.1.233.1740 . doi:10.1145/2213977.2214082. ISBN   978-1-4503-1245-5.
  18. Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
  19. Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN   0-471-46983-1.
  20. Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12