Fibonacci Heap

A Fibonacci heap is a specific implementation of the heap data structure that makes use of Fibonacci numbers. Fibonacci heaps are used to implement the priority queue element in Dijkstra’s algorithm, giving the algorithm a very efficient running time.

Fibonacci heaps have a faster amortized running time than other heap types. Fibonacci heaps are similar to binomial heaps but Fibonacci heaps have a less rigid structure. Binomial heaps merge heaps immediately but Fibonacci heaps wait to merge until the extract-min function is called. While Fibonacci heaps have very good theoretical complexities, in practice, other heap types such as pairing heaps are faster. This is because even in the simplest implementation, Fibonacci heaps require four pointers for each node, other heaps need two or three.^[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)^[2]

As the name suggests, Fibonacci heaps use Fibonacci numbers in its structure.

The Fibonacci numbers are the terms of a sequence of integers in which each term is the sum of the two previous terms with \[\begin{array} &F_1 = F_2 = 1, &F_n = F_{n-1} + F_{n-2}.\ _\square\end{array}\]

The first few Fibonacci numbers are \[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \ldots\]

Like binomial heaps, Fibonacci heaps use doubly linked lists to allow for \(O(1)\) time for operations such as splicing off a part of a list, merging two lists, and finding the minimum (or maximum) value. Each node contains a pointer to its parent and any one of its children. The children are all linked together in a doubly linked list called the child list. Each child in the child list has pointers for its left sibling and its right sibling.

For each node, the linked list also maintains the number of children a node has, a pointer to the root containing the minimum key, and whether the node is marked. A node is marked to indicate that it has lost a single child and a node is unmarked if it loses no children. See the description of the decrease-key function in the next section for more details.

Here is an image showing the differences between a singly linked list and a doubly-linked list. The singly linked has only one pointer from each node, while the doubly linked has pointers going both to and from a node. ^{[3] [4]}

In Fibonacci heaps, the degrees of nodes (the number of children) are constrained. Each node in the heap has degree at most \(O(\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^[5]. This structure is maintained by having a rule that at most one child can be cut from each non-root node. When a second child is removed, the node itself needs to be removed from its parent and becomes the root of a new tree. This means that the number of trees is decreased in the operation extract-min, where trees are linked together.

Fibonacci heaps must satisfy the min-heap property (or max-heap property if making a max-heap) where every node’s children must have a smaller value than it (the parent), and therefore, the minimum element will always be at the root of one of the trees.

Here is how Fibonacci heaps implement the basic functionalities of heaps and the time complexity of each operation. The children of each node are also related using a linked list. For each node, the linked list maintains the number of children a node has and whether the node is marked. The linked list also maintains a pointer to the root containing the minimum key. A node is marked to indicate if any of its children were removed. This is important so the heap can keep track of how far removed its shape is becoming from a binomial heap. If a Fibonacci heap is too different from a binomial heap, it loses many of the efficient time operations that their binomial nature gives it.

These operations are described in terms of a min Fibonacci heap, but they could easily be adapted to be max Fibonacci heap operations.

Find Minimum

The linked list has pointers and keeps track of the minimum node, so finding the minimum is simple and can be done in constant time.

Merge

In Fibonacci heaps, merging is accomplished by simply concatenating two lists containing the tree roots. Compare the roots of the two heaps to be merged, and whichever is smaller becomes the root of the new combined heap. The other tree is added as a subtree to this root. This can be done in constant time.

Explain why Fibonacci heaps allow for constant time merging. What does this mean for the insert operation?

Show Answer

Concatenating the two lists can be done in constant time. Doing operations to a linked list is constant time since it is just a matter of updating pointers. Comparing the roots of two heaps is also constant time.

Sinceinsert is just taking the node to be inserted and treating it like a heap to be merged with the heap we are inserting the node into, we just call merge on the two. This means that insert is also constant time.

Extract Minimum

extract-min is one of the most important operations regarding Fibonacci heaps. Much of a Fibonacci heap’s speed advantage comes from the fact that it delays consolidating heaps after operations until extract-min is called. Binomial heaps, on the other hand, consolidate immediately. Consolidation occurs when heap properties are violated, for example, if two heaps have the same order, the heaps must be adjusted to prevent this.

Deleting the minimum element is done in three steps. The node is removed from the root list and the node’s children are added to the root list. Next, the minimum element is updated if needed. Finally, consolidate the trees so that there are no repeated orders. If any consolidation occurred, make sure to update the minimum element if needed. Delyaing consolidation saves times.

The two images below show the extract-min function on the Fibonacci heap shown in the introduction.

Fibonacci heap after the first phase of extract minimum. Node with key 1 (the minimum) was deleted and its children were added as separate trees.^[6]

Fibonacci after extract minimum is completed. First, nodes 3 and 6 are linked together. Then the result is linked with tree rooted at node 2. Finally, the new minimum is found.^[7]

Insert

Insertion to a Fibonacci heap is similar to the insert operation of a binomial heap. A heap of one element is created and the two heaps are merged with the merge function. The minimum element pointer is updated if necessary. The total number of nodes in the tree increases by one.

Remove

To delete an element, decrease the key using decrease key to negative infinity, and then call extract-min. When the node has a value of negative infinity, since the heap is a min heap, it will become the root of the tree. extract-min will remove the top element, so doing this deletes the node in question.

Decrease Key

There are two situations that can arise when decreasing the key: the change will cause a heap violation or it will not.

• If the heap properties aren’t violated, simply decrease \(x\).

• If a violation does occur, remove the node its parent. If the parent is not a root, mark it. If it has been marked already, it is removed as well and its parent is marked, and so on. Continue this process up the tree until either the root or an unmarked node is reached. Next, set the minimum pointer to the decreased value if it is the new minimum.^[5]

Fibonacci heap from the introduction after decreasing key of node 9 to 0. This node, as well as its two marked ancestors, are cut from the tree rooted at 1 and placed as new roots.^[8]

The decrease key function marks a node when its child is removed. This allows it to track some history about each node. Essentially the marking tracks if^[9]:

• The node has had no children removed (unmarked)
• The node has had a single child removed (marked)
• The node is about to have a second child removed (removing a child of a marked node)

Here is a pseudocode implementation of Fibonacci heaps^{[10] [11]}.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

Make-Fibonacci-Heap()
n[H] := 0
min[H] := NIL 
return H

Fibonacci-Heap-Minimum(H)
return min[H]

Fibonacci-Heap-Link(H,y,x)
remove y from the root list of H
make y a child of x
degree[x] := degree[x] + 1
mark[y] := FALSE

CONSOLIDATE(H)
for i:=0 to D(n[H])
     Do A[i] := NIL
for each node w in the root list of H
    do x:= w
       d:= degree[x]
       while A[d] <> NIL
           do y:=A[d]
              if key[x]>key[y]
                then exchange x<->y
              Fibonacci-Heap-Link(H, y, x)
              A[d]:=NIL
             d:=d+1
       A[d]:=x
min[H]:=NIL
for i:=0 to D(n[H])
    do if A[i]<> NIL
          then add A[i] to the root list of H
               if min[H] = NIL or key[A[i]]<key[min[H]]
                  then min[H]:= A[i]

Fibonacci-Heap-Union(H1,H2)
H := Make-Fibonacci-Heap()
min[H] := min[H1]
Concatenate the root list of H2 with the root list of H
if (min[H1] = NIL) or (min[H2] <> NIL and min[H2] < min[H1])
   then min[H] := min[H2]
n[H] := n[H1] + n[H2]
free the objects H1 and H2
return H


Fibonacci-Heap-Insert(H,x)
degree[x] := 0
p[x] := NIL
child[x] := NIL
left[x] := x
right[x] := x
mark[x] := FALSE
concatenate the root list containing x with root list H
if min[H] = NIL or key[x]<key[min[H]]
        then min[H] := x
n[H]:= n[H]+1

Fibonacci-Heap-Extract-Min(H)
z:= min[H]
if x <> NIL
        then for each child x of z
             do add x to the root list of H
                p[x]:= NIL
             remove z from the root list of H
             if z = right[z]
                then min[H]:=NIL
                else min[H]:=right[z]
                     CONSOLIDATE(H)
             n[H] := n[H]-1
return z

Fibonacci-Heap-Decrease-Key(H,x,k)
if k > key[x]
   then error "new key is greater than current key"
key[x] := k
y := p[x]
if y <> NIL and key[x]<key[y]
   then CUT(H, x, y)
        CASCADING-CUT(H,y)    
if key[x]<key[min[H]]
   then min[H] := x

CUT(H,x,y)
Remove x from the child list of y, decrementing degree[y]
Add x to the root list of H
p[x]:= NIL
mark[x]:= FALSE

CASCADING-CUT(H,y)
z:= p[y]
if z <> NIL
  then if mark[y] = FALSE
       then mark[y]:= TRUE
       else CUT(H, y, z)
            CASCADING-CUT(H, z)

Fibonacci-Heap-Delete(H,x)
Fibonacci-Heap-Decrease-Key(H,x,-infinity)
Fibonacci-Heap-Extract-Min(H)

Python implementations of Fibonacci heaps can be quite long, but here is an example Python implementation.

According to a paper^[12] written by Michael Fredman (one of the inventors of Fibonacci heaps), Fibonacci heaps have a couple of downsides: many computer scientists claim that they are difficult to program and their theoretically excellent running times aren't always better in practice than theoretically inferior types of heaps.

• Binary Heaps

• Binomial Heaps

• Pairing Heaps

• Heap Sort

1. , . Fibonacci_Heap. Retrieved June 25, 2016, from https://en.wikipedia.org/wiki/Fibonacci_heap
2. , B. Fibonacci_Heap. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/File:Fibonacci_heap.png
3. , L. Doubly-linked-list.svg. Retrieved June 25, 2016, from https://en.wikipedia.org/wiki/File:Doubly-linked-list.svg
4. , L. Singly-linked-list.svg. Retrieved June 25, 2016, from https://en.wikipedia.org/wiki/File:Singly-linked-list.svg
5. , . Fibonacci heap. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/Fibonacci_heap
6. , M. Fibonacci heap extractmin1.png. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/File:Fibonacci_heap_extractmin1.png
7. , B. Fibonacci heap extractmin2.png. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/File:Fibonacci_heap_extractmin2.png
8. , B. Fibonacci heap-decreasekey.png. Retrieved June 7, 2016, from https://en.wikipedia.org/wiki/File:Fibonacci_heap-decreasekey.png
9. Imms, D. Fibonacci Heap. Retrieved June 7, 2016, from http://www.growingwiththeweb.com/2014/06/fibonacci-heap.html
10. Stergiopoulos , S. Algorithm for Fibonacci Heap Operations. Retrieved June 7, 2016, from http://www.cse.yorku.ca/~aaw/Sotirios/BinomialHeapAlgorithm.html
11. Cormen, T., Leiserson, C., Rivest, R., & Stein, C. (2001). Introduction to Algorithms (2nd edition) (pp. chapter 20). The MIT Press.
12. Fredman, M., Sedgewick, R., Sleator, D., & Tarjan, R. The Pairing Heap: A New Form of Self-Adjusting Heap. Retrieved June 7, 2016, from https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf