The potential of a Fibonacci heap is given by The amount of time saved for later use is measured at any given moment by a potential function. This additional time is then later combined and subtracted from the actual running time of slow operations. 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. The number of trees is decreased in the operation delete minimum, where trees are linked together.Īs a result of a relaxed structure, some operations can take a long time while others are done very quickly. 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). This is achieved by the rule that we can cut at most one child of each non-root node. In particular, degrees of nodes (here degree means the number of direct children) are kept quite low: every node has degree at most log n and the size of a subtree rooted in a node of degree k is at least F k+2, where F k is the kth Fibonacci number. However, at some point order needs to be introduced to the heap to achieve the desired running time. 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. This flexibility allows some operations to be executed in a lazy manner, postponing the work for later operations. The trees do not have a prescribed shape and in the extreme case the heap can have every element in a separate tree. Compared with binomial heaps, the structure of a Fibonacci heap is more flexible. This implies that the minimum key is always at the root of one of the trees. Therefore, the potential of the heap is 9 (3 trees + 2 × (3 marked-vertices)).Ī 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. Three vertices are marked (shown in blue). It has three trees of degrees 0, 1 and 3. Using Fibonacci heaps for priority queues improves the asymptotic running time of important algorithms, such as Dijkstra's algorithm for computing the shortest path between two nodes in a graph, compared to the same algorithm using other slower priority queue data structures. 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. A Fibonacci heap is thus better than a binary or binomial heap when b is smaller than a by a non-constant factor. In a binary or binomial heap, such a sequence of operations would take O(( a + b) log n) time. This means that starting from an empty data structure, any sequence of a insert and decrease key operations and b delete operations would take O( a + b log n) worst case time, where n is the maximum heap size. Deleting an element (most often used in the special case of deleting the minimum element) works in O(log n) amortized time, where n is the size of the heap. The insert and decrease key operations also work in constant amortized time. Fibonacci heaps are named after the Fibonacci numbers, which are used in their running time analysis.įor the Fibonacci heap, the find-minimum operation takes constant ( O(1)) amortized time. Tarjan developed Fibonacci heaps in 1984 and published them in a scientific journal in 1987. It has a better amortized running time than many other priority queue data structures including the binary heap and binomial heap. In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. Data structure for priority queue operations Fibonacci heap
0 kommentar(er)
