Fibonacci-Heap

In computer science, a Fibonacci heap is (english heap, heap ') a data structure similar to a binomial heap that implements a priority queue. This means that elements with fixed-priority can be stored in any order efficiently in the heap, and always an element with the highest priority can be removed. The priority of the items will be impressed by this key. Must therefore be on the set of keys, a total ordering exist, as represented, for example, the less-than relation ( < ) over the integers. Fibonacci heaps were first described in 1984 by Michael L. Fredman and Robert E. Tarjan. Your name stems from the analysis of the data structure, they play a major role in the Fibonacci numbers.

Operations

Fibonacci heaps efficiently support the operations:

• Insert - to insert an element
• Remove or delete - to remove an element
• GetMin - for finding the element with the minimum key
• ExtractMin - to return and for removing an element with minimum key ( = highest priority)
• Decreasekey - to decrease the key of an element and
• Merge or union - for merging two heaps.

Maturities

All operations can be personalized with a logarithmic worst-case running time, ie, implement, where n is the number of elements currently in the heap is. Only the operations remove, extractMin and decreasekey need in the worst-case linear term, ie. Pays for the cost of almost all other operations, however, are constant, ie.

Consequently, - at amortized runtime analysis - Fibonacci Heaps Heaps binary or binomial heaps insert in the execution of operations and merge superior. However, they are due to the poor worst-case running time of remove, extractMin and decreasekey less for online algorithms where each operation has to be performed efficiently.

Maturities compared:

(*) Amortized cost (¹) With a known position, otherwise O ( log n) *

Description of the data structure

A Fibonacci heap is a list of trees with ordered successors, whose nodes and may include a marking key. The impressed by the key priority of each node is at least as large as the priority of his children. This is called heap condition. In the min - heap shown here that greater priority is represented by a smaller key.

Cyclic doubly-linked lists are used for both the list of trees as well as the lists of child nodes in the nodes of the trees.

In addition, a pointer is maintained on the element with the highest priority (smallest key ).

A Fibonacci heap is called normalized if all the trees have different root level, that is, if the roots of the trees in the list all have a different number of child nodes.

Implementation of operations

Insert operation

When inserting an element by means of this insert is simply inserted as a separate tree in the list of trees and redraw the pointer to the minimum element if the key of the inserted element is less than the minimum of the previous element. The term is therefore constant:

Merge operation

Similarly, simple design, the fusion of two heaps by merge. Here are the lists of the merging trees are simply concatenated and the pointer if necessary, converted to the minimal element if the key of the minimum element of the added heap is smaller than the minimum of the previous element. The running time is again constant:

Operation decreasekey

The operation is performed decreasekey quite lazy in a Fibonacci heap: The key of the element to be updated is first set to the new value. Now it may be that the heap property (all children greater than the father) is no longer fulfilled. To restore this, you delete the updated item from the child list of its parent node and adds it as a separate tree in the "List of Trees" / root list.

To avoid that by such operations, the heap too much grows in width ( then would extractMin take a long time ), it now represents the condition that each node only one child node must be removed, otherwise the node must itself from the child list be its father node removed (Procedure Cut) etc. In order to realize this now takes the above-mentioned labeling a node in appearance: a node if and only marked if it is not the root node list and a child was removed from its child list. Now if a child away, whose father was marked by calling the procedure recursively Cut to the father. It is found after careful mathematical analysis that the number of nodes in a tree of degree (ie, the root of the tree has children) is then limited by the - th Fibonacci number down, the golden ratio. This is for the function extractMin of enormous importance.

Operation extractMin

Now to the central function: extractMin. The beginning of this function is rather simple: the minimal element that yes, a pointer is output, all its children are added as individual trees to the root list, and the element itself is removed from the heap. Now a new minimum has to be determined. However, since none of the previous functions of the heap to grow in depth, this would take a linear time. Therefore, the heap before the cleanup procedure " cleaned up ". Thereafter, all members of the root list are gone to find a new minimum.

The procedure cleanup: For this purpose an array of up is first initialized. In this in place after the cleanup is a pointer standing on a tree when the root list an item with degrees exist. All members of the root list, so it will be classified in this array. Is it relevant to an overlap (two elements have the same degree ), then the element with the smaller key is made the father of the other, the degree thereof is increased and it is sorted in the array. The above mathematical analysis assures that at most elements in the array are. Finally, the new root list must be built. For this, all elements of the array are processed and merged into one list. The term is so.

Operation remove

Is performed to remove an element from the heap by means remove by first decreasekey with the key of the element to be removed is set to a value smaller than the previous minimum. Thus, this element is the new minimum element. Then it can be removed with extractMin. The term of decreasekey is constant, the amounts of extractMin, therefore results for the surgery remove a term of also.

Comments

The operations and remove decreasekey assume that you know the position of the corresponding elements in the heap. Generally, it is namely not possible to efficiently search for an item in the heap. Therefore, the operation must insert return a pointer to the container for the inserted element to the calling program remembers at a suitable location in case of need.

Applications

The Dijkstra's algorithm for finding a shortest path or the algorithm of Prim for finding a minimal spanning tree of a graph with n vertices and m edges can be implemented with the maturity of with Fibonacci heaps. With a binary or binomial heap here would only be possible maturities of.