In Chapter 20, we saw how binomial heaps support in *O*(lg *n*) worst-case time the mergeable-heap operations INSERT, MINIMUM, EXTRACT-MIN, and UNION, plus the operations DECREASE-KEY and DELETE. In this chapter, we shall examine Fibonacci heaps, which support the same operations but have the advantage that operations that do not involve deleting an element run in *O*(1) amortized time.

Unlike trees within binomial heaps, which are ordered, trees within Fibonacci heaps are rooted but unordered. As Figure 21.1(b) shows, each node *x* contains a pointer *p*[*x*] to its parent and a pointer *child*[*x*] to any one of its children. The children of *x* are linked together in a circular, doubly linked list , which we call the **child list*** *of *x*. Each child *y* in a child list has pointers *left*[*y*] and *right*[*y*] that point to *y*'s left and right siblings, respectively. If node *y* is an only child, then *left*[*y*] = *right*[*y*] = *y*. The order in which siblings appear in a child list is arbitrary.

Two other fields in each node will be of use. The number of children in the child list of node *x* is stored in *degree*[*x*]. The boolean-valued field *mark*[*x*] indicates whether node *x h*as lost a child since the last time *x* was made the child of another node. We won't worry about the details of marking nodes until Section 21.3. Newly created nodes are unmarked, and a node *x* becomes unmarked whenever it is made the child of another node.

A given Fibonacci heap *H* is accessed by a pointer *min*[*H*] to the root of the tree containing a minimum key; this node is called the * minimum node* of the Fibonacci heap. If a Fibonacci heap

The roots of all the trees in a Fibonacci heap are linked together using their *left* and *right* pointers into a circular, doubly linked list called the **root*** list* of the Fibonacci heap. The pointer

As mentioned, we shall use the potential method of Section 18.3 to analyze the performance of Fibonacci heap operations. For a given Fibonacci heap *H*, we indicate by *t*(*H*) the number of trees in the root list of *H* and by *m *(*H*) the number of marked nodes in *H*. The potential of Fibonacci heap *H* is then defined by

(H) =t(H) + 2m(H) .

The amortized analyses we shall perform in the remaining sections of this chapter assume that there is a known upper bound *D*(*n*) on the maximum degree of any code in an *n-*node Fibonacci heap. Exercise 21.2-3 shows that when only the mergeable-heap operations are supported, *D*(*n*) = lg *n**.* In Section 21.3, we shall show that when we support DECREASE-KEY and DELETE as well, *D*(*n*) = *O*(lg *n*).

In this section, we describe and analyze the mergeable-heap operations as implemented for Fibonacci heaps. If only these operations--MAKE-HEAP, INSERT, MINIMUM, EXTRACT-MIN, and UNION--are to be supported, each Fibonacci heap is simply a collection of "unordered" binomial trees. An **unordered binomial tree*** *is like a binomial tree, and it, too, is defined recursively. The unordered binomial tree *U*_{0} consists of a single node, and an unordered binomial tree *U _{k}* consists of two unordered binomial trees

Thus, if an *n*-node Fibonacci in heap is a collection of unordered binomial trees, then *D*(*n*) = lg *n*.

To make an empty Fibonacci heap, the MAKE-FIB-HEAP procedure allocates and returns the Fibonacci heap object *H*, where *n*[*H*] = 0 and *min*[*H*] = NIL; there are no trees in *H.* Because *t *(*H*) = 0 and *m*(*H*) = 0, the potential of the empty Fibonacci heap is (*H*) = 0. The amortized cost of MAKE-FIB-HEAP is thus equal to its *O*(1) actual cost.

The following procedure inserts node *x* into Fibonacci heap *H*, assuming of course that the node has already been allocated and that *key*[*x*] has already been filled in.

FIB-HEAP-INSERT(H,x)

1degree[x] 0

2p[x] NIL

3child[x] NIL

4left[x]x

5right[x]x

6mark[x] FALSE

7 concatenate the root list containingxwith root listH

8ifmin[H] = NIL orkey[x] <key[min[H]]

9thenmin[H]x

10n[H]n[H] + 1

((t(H) + 1) + 2m(H)) - (t(H) + 2m(H)) = 1 .

Since the actual cost is *O*(1), the amortized cost is *O*(1) + 1 = *O*(1).

The minimum node of a Fibonacci heap *H* is given by the pointer *min*[*H*], so we can find the minimum node in *O*(1) actual time. Because the potential of *H* does not change, the amortized cost of this operation is equal to its *O*(1) actual cost.

The following procedure unites Fibonacci heaps *H*_{1} and *H*_{2}, destroying *H*_{1 }and *H*_{2} in the process.

FIB-HEAP-UNION(H_{1,}H_{2})

1HMAKE-FIB-HEAP()

2min[H]min[H_{1}]

3 concatenate the root list ofH_{2}with the root list ofH

4if(min[H_{1}] = NIL) or (min[H_{2}] NIL andmin[H_{2}] <min[H_{1}])

5thenmin[H]min[H_{2}]

6n[H]n[H_{1}] +n[H_{2}]

7 free the objectsH_{1}andH_{2}

8returnH

(H) - ((H_{1}) + (H_{2}))

= (t(H) + 2m(H)) - ((t(H_{1}) + 2m(H_{1})) + (t(H_{2}) + 2m(H_{2})))

= 0,

The process of extracting the minimum node is the most complicated of the operations presented in this section. It is also where the delayed work of consolidating trees in the root list finally occurs. The following pseudocode extracts the minimum node. The code assumes for convenience that when a node is removed from a linked list, pointers remaining in the list are updated, but pointers in the extracted node are left unchanged. It also uses the auxiliary procedure CONSOLIDATE, which will be presented shortly.

FIB-HEAP-EXTRACT-MIN(H)

1zmin[H]

2ifzNIL

3then foreach childxofz

4doaddxto the root list ofH

5p[x] NIL

6 removezfrom the root list ofH

7ifz=right[z]

8thenmin[H] NIL

9elsemin[H]right[z]

10 CONSOLIDATE(H)

11n[H]n[H] - 1

12returnz

The next step, in which we reduce the number of trees in the Fibonacci heap, is * consolidating* the root list of

1. Find two roots *x* and *y* in the root list with the same degree, where *key*[*x*] *key*[*y*].

2. **Link***y* to *x*: remove *y* from the root list, and make *y* a child of *x*. This operation is performed by the FIB-HEAP-LINK procedure. The field *degree*[*x*] is incremented, and the mark on *y*, if any, is cleared.

The procedure CONSOLIDATE uses an auxiliary array *A*[0 . . *D*(*n*[*H*])]; if *A*[*i*] = *y*, then *y* is currently a root with *degree*[*y*] = *i*.

CONSOLIDATE(H)

1fori0toD(n[H])

2doA[i] NIL

3foreach nodewin the root list ofH

4doxw

5ddegree[x]

6whileA[d] NIL

7doyA[d]

8ifkey[x] >key[y]

9thenexchangexy

10 FIB-HEAP-LINK(H,y,x)

11A[d] NIL

12dd+ 1

13A[d]x

14min[H] NIL

15fori0toD(n[H])

16do ifA[i] NIL

17thenaddA[i] to the root list ofH

18ifmin[H] = NIL orkey[A[i]] <key[min[H]]

19thenmin[H]A[i]

FIB-HEAP-LINK(H, y, x)

1 removeyfrom the root list ofH

2 makeya child ofx, incrementingdegree[x]

3mark[y] FALSE

We are now ready to show that the amortized cost of extracting the minimum node of an *n*-node Fibonacci heap is *O*(*D*(*n*)). Let *H* denote the Fibonacci heap just prior to the FIB-HEAP-EXTRACT-MIN operation.

The potential before extracting the minimum node is *t*(*H*) + 2*m*(*H*), and the potential afterward is at most (*D*(*n*) + 1) + 2*m*(*H*), since at most *D*(*n*) + 1 roots remain and no nodes become marked during the operation. The amortized cost is thus at most

O(D(n) +t(H)) + ((D(n) + 1) + 2m(H)) - (t(H) + 2m(H))

=O(D(n)) +O(t(H)) -t(H)

=O(D(n)),

Show that if only the mergeable-heap operations are supported, the maximum degree *D(n)* in an *n*-node Fibonacci heap is at most 1g *n*.

Professor McGee has devised a new data structure based on Fibonacci heaps. A McGee heap has the same structure as a Fibonacci heap and supports the mergeable-heap operations. The implementations of the operations are the same as for Fibonacci heaps, except that insertion and union perform consolidation as their last step. What are the worst-case running time of operations on McGee heaps? How novel is the professor's data structure?

Argue that when the only operations on keys are comparing two keys (as is the case for all the implementations in this chapter), not all of the mergeable-heap operations can run in *O*(1) amortized time.

In this section, we show how to decrease the key of a node in a Fibonacci heap in *O*(1) amortized time and how to delete any node from an *n*-node Fibonacci heap in *O*(*D*(*n*)) amortized time. These operations do not preserve the property that all trees in the Fibonacci heap are unordered binomial trees. They are close enough, however, that we can bound the maximum degree *D*(*n*) by *O*(1g *n*). Proving this bound will imply that FIB-HEAP-EXTRACT-MIN and FIB-HEAP-DELETE run in *O*(1g *n*) amortized time.

FIB-HEAP-DECREASE-KEY(H,x,k)

1ifk>key[x]

2then error"new key is greater than current key"

3key[x]k

4yp[x]

5ifyNIL andkey[x] <key[y]

6thenCUT(H,x,y)

7 CASCADING-CUT(H,y)

8ifkey[x] <key[min[H]]

9thenmin[H]x

CUT(H,x,y)

1 removexfrom the child list ofy, decrementingdegree[y]

2 addxto the root list ofH

3p[x] NIL

4mark[x] FALSE

CASCADING-CUT(H,y)

1zp[y]

2ifzNIL

3then ifmark[y] = FALSE

4thenmark[y] TRUE

5elseCUT(H,y,z)

6 CASCADING-CUT(H,z)

If heap order has been violated, many changes may occur. We start by **cutting***x* in line 6. The CUT procedure "cuts" the link between *x* and its parent *y*, making *x* a root.

We use the *mark* fields to obtain the desired time bounds. They help to produce the following effect. Suppose that *x* is a node that has undergone the following history:

1. at some time, *x* was a root,

2. then *x* was linked to another node,

3. then two children of *x* were removed by cuts.

We are not yet done, because *x* might be the second child cut from its parent *y* since the time that *y* was linked to another node. Therefore, line 7 of FIB-HEAP-DECREASE-KEY performs a * cascading-cut* operation on

We shall now show that the amortized cost of FIB-HEAP-DECREASE-KEY is only *O*(1). We start by determining its actual cost. The FIB-HEAP-DECREASE-KEY procedure takes *O*(1) time, plus the time to perform the cascading cuts. Suppose that CASCADING-CUT is recursively called *c* times from a given invocation of FIB-HEAP-DECREASE-KEY. Each call of CASCADING-CUT takes *O*(1) time exclusive of recursive calls. Thus, the actual cost of FIB-HEAP-DECREASE-KEY, including all recursive calls, is *O*(*c*).

We next compute the change in potential. Let *H* denote the Fibonacci heap just prior to the FIB-HEAP-DECREASE-KEY operation. Each recursive call of CASCADING-CUT, except for the last one, cuts a marked node and clears the mark bit. Afterward, there are *t*(*H*) + *c* trees (the original *t*(*H*) trees, *c*- 1 trees produced by cascading cuts, and the tree rooted at *x*) and at most *m*(*H*) - *c* + 2 marked nodes (*c* - 1 were unmarked by cascading cuts and the last call of CASCADING-CUT may have marked a node). The change in potential is therefore at most

((t(H) +c) + 2(m(H) -c+ 2)) - (t(H) + 2m(H)) = 4 -c.

Thus, the amortized cost of FIB-HEAP-DECREASE-KEY is at most

O(c) + 4 -c=O(1) ,

since we can scale up the units of potential to dominate the constant hidden in *O*(*c*).

It is easy to delete a node from an *n*-node Fibonacci heap in *O*(*D*(*n*)) amortized time, as is done by the following pseudocode. We assume that there is no key value of - currently in the Fibonacci heap.

FIB-HEAP-DELETE(H, x)

1 FIB-HEAP-DECREASE-KEY(H,x, -)

2 FIB-HEAP-EXTRACT-MIN(H)

Suppose that a root *x* in a Fibonacci heap is marked. Explain how *x* came to be a marked root. Argue that it doesn't matter to the analysis that *x* is marked, even though it is not a root that was first linked to another node and then lost one child.

Justify the *O*(1) amortized time of FIB-HEAP-DECREASE-KEY using the aggregate method of Section 18.1.

To prove that the amortized time of FIB-HEAP-EXTRACT-MIN and FIB-HEAP-DELETE is *O*(l*g n*), we must show that the upper bound *D*(*n*) on the degree of any node of an *n*-node Fibonacci heap is *O*(lg *n*). By Exercise 21.2-3, when all trees in the Fibonacci heap are unordered binomial trees, *D(n)* = lg *n*. The cuts that occur in FIB-HEAP-DECREASE-KEY, however, may cause trees within the Fibonacci heap to violate the unordered binomial tree properties. In this section, we shall show that because we cut a node from its parent as soon as it loses two children, *D*(*n*) is *O*(lg *n*). In particular, we shall show that *D*(*n*) log_{ n}, where .

* Proof *Obviously,

We finally come to the part of the analysis that explains the name "Fibonacci heaps." Recall from Section 2.2 that for *k* = 0, 1, 2, . . . , the *k*th Fibonacci number is defined by the recurrence

The following lemma gives another way to express *F _{k}*.

* Proof *The proof is by induction on

We now assume the inductive hypothesis that , and we have

F+2_{k}^{k },

where is the golden ratio defined in equation (2.14) as .

Let *x *be any node in a Fibonacci heap, and let *k* = *degree*[*x*]. Then, size (*x*) *F _{k}*+2

The last equality follows from Lemma 21.2.

Thus, we have shown that size(*x*) *s _{k }*+ 2

The maximum degree *D*(*n*) of any node in an *n*-node Fibonacci heap is *O*(lg *n*).

Professor Pinocchio claims that the height of an *n*-node Fibonacci heap is *O*(lg *n*). Show that the professor is mistaken by exhibiting, for any positive integer *n*, a sequence of Fibonacci-heap operations that creates a Fibonacci heap consisting of just one tree that is a linear chain of *n* nodes.

Suppose we generalize the cascading-cut rule to cut a node *x* from its parent as soon as it loses its *k*th child, for some integer constant *k*. (The rule in Section 21.3 uses *k* = 2.) For what values of *k* is *D*(*n*) = *O*(lg *n*)?

21-1 Alternative implementation of deletion

Professor Pisano has proposed the following variant of the FIB-HEAP-DELETE procedure, claiming that it runs faster when the node being deleted is not the node pointed to by *min*[*H*].

PISANO-DELETE(H, x)

1ifx=min[H]

2thenFIB-HEAP-EXTRACT-MIN(H)

3elseyp[x]

4ifyNIL

5thenCUT(H,x,y)

6 CASCADING-CUT(H,y)

7 addx's child list to the root list ofH

8 removexfrom the root list ofH

21-2 More Fibonacci-heap operations

We wish to augment a Fibonacci heap *H* to support two new operations without changing the amortized running time of any other Fibonacci-heap operations.

Fibonacci heaps were introduced by Fredman and Tarjan [75]. Their paper also describes the application of Fibonacci heaps to the problems of single-source shortest paths, all-pairs shortest pairs, weighted bipartite matching, and the minimum-spanning-tree problem.

Subsequently, Driscoll, Sarnak, Sleator, and Tarjan [58] developed "relaxed heaps" as an alternative to Fibonacci heaps. There are two varieties of relaxed heaps. One gives the same amortized time bounds as Fibonacci heaps. The other allows DECREASE-KEY to run in *O*(1) worst-case (not amortized) time and EXTRACT-MIN and DELETE to run in *O*(lg *n*) worst-case time. Relaxed heaps also have some advantages over Fibonacci heaps in parallel algorithms.