Algorithms Non-Lecture L: Fibonacci Heaps

A little and a little, collected together, become a great deal; the heap in the barn
consists of single grains, and drop and drop makes an inundation.
Saadi (11841291)
The trees that are slow to grow bear the best fruit.
Molire (16221673)
Promote yourself but do not demote another.
Rabbi Israel Salanter (18101883)
Fall is my favorite season in Los Angeles, watching the birds change color and fall
from the trees.
David Letterman
L Fibonacci Heaps
L.1 Mergeable Heaps
A mergeable heap is a data structure that stores a collection of keys
1
and supports the following operations.
INSERT: Insert a new key into a heap. This operation can also be used to create a new heap
containing just one key.
FINDMIN: Return the smallest key in a heap.
DELETEMIN: Remove the smallest key from a heap.
MERGE: Merge two heaps into one. The new heap contains all the keys that used to be in the old
heaps, and the old heaps are (possibly) destroyed.
If we never had to use DELETEMIN, mergeable heaps would be completely trivial. Each heap just
stores to maintain the single record (if any) with the smallest key. INSERTs and MERGEs require only
one comparison to decide which record to keep, so they take constant time. FINDMIN obviously takes
constant time as well.
If we need DELETEMIN, but we dont care how long it takes, we can still implement mergeable
heaps so that INSERTs, MERGEs, and FINDMINs take constant time. We store the records in a circular
doubly-linked list, and keep a pointer to the minimum key. Now deleting the minimum key takes (n)
time, since we have to scan the linked list to nd the new smallest key.
In this lecture, Ill describe a data structure called a Fibonacci heap that supports INSERTs, MERGEs,
and FINDMINs in constant time, even in the worst case, and also handles DELETEMIN in O(log n) amortized
time. That means that any sequence of n INSERTs, m MERGEs, f FINDMINs, and d DELETEMINs takes
O(n +m+ f +d log n) time.
L.2 Binomial Trees and Fibonacci Heaps
A Fibonacci heap is a circular doubly linked list, with a pointer to the minimum key, but the elements of the
list are not single keys. Instead, we collect keys together into structures called binomial heaps. Binomial
heaps are trees that satisfy the heap propertyevery node has a smaller key than its childrenand have
the following special recursive structure.
A kth order binomial tree, which Ill abbreviate B
k
, is dened recursively. B
0
is a single node. For all
k > 0, B
k
consists of two copies of B
k1
that have been linked together, meaning that the root of one
B
k1
has become a new child of the other root.
1
In the earlier lecture on treaps, I called these keys priorities to distinguish them from search keys.
1
Algorithms Non-Lecture L: Fibonacci Heaps
B
4
B
4
5
B
Binomial trees of order 0 through 5.
Binomial trees have several useful properties, which are easy to prove by induction (hint, hint).
The root of B
k
has degree k.
The children of the root of B
k
are the roots of B
0
, B
1
, . . . , B
k1
.
B
k
has height k.
B
k
has 2
k
nodes.
B
k
can be obtained from B
k1
by adding a new child to every node.
B
k
has

k
d

nodes at depth d, for all 0 d k.

B
k
has 2
kh1
nodes with height h, for all 0 h < k, and one node (the root) with height k.
Although we normally dont care in this class about the low-level details of data structures, we need
to be specic about how Fibonacci heaps are actually implemented, so that we can be sure that certain
operations can be performed quickly. Every node in a Fibonacci heap points to four other nodes: its
parent, its next sibling, its previous sibling, and one of its children. The sibling pointers are used to
join the roots together into a circular doubly-linked root list. In each binomial tree, the children of each
node are also joined into a circular doubly-linked list using the sibling pointers.
min
min
A high-level view and a detailed view of the same Fibonacci heap. Null pointers are omitted for clarity.
With this representation, we can add or remove nodes from the root list, merge two root lists together,
link one two binomial tree to another, or merge a nodes list of children with the root list, in constant
time, and we can visit every node in the root list in constant time per node. Having established that
these primitive operations can be performed quickly, we never again need to think about the low-level
representation details.
2
Algorithms Non-Lecture L: Fibonacci Heaps
L.3 Operations on Fibonacci Heaps
The INSERT, MERGE, and FINDMIN algorithms for Fibonacci heaps are exactly like the corresponding
algorithms for linked lists. Since we maintain a pointer to the minimum key, FINDMIN is trivial. To insert
a new key, we add a single node (which we should think of as a B
0
) to the root list and (if necessary)
update the pointer to the minimum key. To merge two Fibonacci heaps, we just merge the two root lists
and keep the pointer to the smaller of the two minimum keys. Clearly, all three operations take O(1)
time.
Deleting the minimum key is a little more complicated. First, we remove the minimum key from the
root list and splice its children into the root list. Except for updating the parent pointers, this takes O(1)
time. Then we scan through the root list to nd the new smallest key and update the parent pointers of
the new roots. This scan could take (n) time in the worst case. To bring down the amortized deletion
time, we apply a CLEANUP algorithm, which links pairs of equal-size binomial heaps until there is only
one binomial heap of any particular size.
Let me describe the CLEANUP algorithm in more detail, so we can analyze its running time. The
following algorithm maintains a global array B[1.. [lg n|], where B[i] is a pointer to some previously-
visited binomial heap of order i, or NULL if there is no such binomial heap. Notice that CLEANUP
simultaneously resets the parent pointers of all the new roots and updates the pointer to the minimum
key. Ive split off the part of the algorithm that merges binomial heaps of the same order into a separate
subroutine MERGEDUPES.
CLEANUP:
newmin some node in the root list
for i 0 to [lg n|
B[i] NULL
for all nodes v in the root list
parent(v) NULL ()
if key(newmin) > key(v)
newmin v
MERGEDUPES(v)
MERGEDUPES(v):
w B[deg(v)]
while w ,= NULL
B[deg(v)] NULL
if key(v) key(w)
swap v w
remove w from the root list ()
link w to v
w B[deg(v)]
B[deg(v)] v
B
0 1 2 3
v
B
0 1 2 3
v
B
0 1 2 3
v
MergeDupes(v), ensuring that no earlier root has the same degree as v.
Notices that MERGEDUPES is careful to merge heaps so that the heap property is maintainedthe
heap whose root has the larger key becomes a new child of the heap whose root has the smaller key.
This is handled by swapping v and w if their keys are in the wrong order.
The running time of CLEANUP is O(r
/
), where r
/
is the length of the root list just before CLEANUP is
called. The easiest way to see this is to count the number of times the two starred lines can be executed:
line () is executed once for every node v on the root list, and line () is executed at most once for
every node w on the root list. Since DELETEMIN does only a constant amount of work before calling
CLEANUP, the running time of DELETEMIN is O(r
/
) = O(r +deg(min)) where r is the number of roots
before DELETEMIN begins, and min is the node deleted.
3
Algorithms Non-Lecture L: Fibonacci Heaps
Although deg(min) is at most lg n, we can still have r = (n) (for example, if nothing has been
deleted yet), so the worst-case time for a DELETEMIN is (n). After a DELETEMIN, the root list has length
O(log n), since all the binomial heaps have unique orders and the largest has order at most [lg n|.
L.4 Amortized Analysis of DELETEMIN
To bound the amortized cost, observe that each insertion increments r. If we charge a constant cleanup
tax for each insertion, and use the collected tax to pay for the CLEANUP algorithm, the unpaid cost of a
DELETEMIN is only O(deg(min)) = O(log n).
More formally, dene the potential of the Fibonacci heap to be the number of roots. Recall that
the amortized time of an operation can be dened as its actual running time plus the increase in
potential, provided the potential is initially zero (it is) and we never have negative potential (we
never do). Let r be the number of roots before a DELETEMIN, and let r
//
denote the number of roots
afterwards. The actual cost of DELETEMIN is r +deg(min), and the number of roots increases by r
//
r,
so the amortized cost is r
//
+deg(min). Since r
//
= O(log n) and the degree of any node is O(log n),
the amortized cost of DELETEMIN is O(log n).
Each INSERT adds only one root, so its amortized cost is still constant. A MERGE actually doesnt
change the number of roots, since the new Fibonacci heap has all the roots from its constituents and no
others, so its amortized cost is also constant.
L.5 Decreasing Keys
In some applications of heaps, we also need the ability to delete an arbitrary node. The usual way to do
this is to decrease the nodes key to , and then use DELETEMIN. Here Ill describe how to decrease
the key of a node in a Fibonacci heap; the algorithm will take O(log n) time in the worst case, but the
amortized time will be only O(1).
Our algorithm for decreasing the key at a node v follows two simple rules.
1. Promote v up to the root list. (This moves the whole subtree rooted at v.)
2. As soon as two children of any node w have been promoted, immediately promote w.
In order to enforce the second rule, we now mark certain nodes in the Fibonacci heap. Specically, a
node is marked if exactly one of its children has been promoted. If some child of a marked node is
promoted, we promote (and unmark) that node as well. Whenever we promote a marked node, we
unmark it; this is theonly way to unmark a node. (Specically, splicing nodes into the root list during a
DELETEMIN is not considered a promotion.)
Heres a more formal description of the algorithm. The input is a pointer to a node v and the new
value k for its key.
DECREASEKEY(v, k):
key(v) k
update the pointer to the smallest key
PROMOTE(v)
PROMOTE(v):
unmark v
if parent(v) ,= NULL
remove v from parent(v)s list of children
insert v into the root list
if parent(v) is marked
PROMOTE(parent(v))
else
mark parent(v)
4
Algorithms Non-Lecture L: Fibonacci Heaps
The PROMOTE algorithm calls itself recursively, resulting in a cascading promotion. Each consecutive
marked ancestor of v is promoted to the root list and unmarked, otherwise unchanged. The lowest
unmarked ancestor is then marked, since one of its children has been promoted.
a
b c d e
f g h i j k
l m n o
p
a
b c d e
f
g h i j k
l m
n o
p
a
b c
d
e
f
g h i j
k l m
n o
p
d
k
j
c
i
o
b
g h
n
a
e
f
l m
p
f
l m
p
d
k
j
c
i
o
a
e
h b
g
n
Decreasing the keys of four nodes: rst f , then d, then j, and nally h. Dark nodes are marked.
DecreaseKey(h) causes nodes b and a to be recursively promoted.
The time to decrease the key of a node v is O(1 +#consecutive marked ancestors of v). Binomial
heaps have logarithmic depth, so if we still had only full binomial heaps, the running time would be
O(log n). Unfortunately, promoting nodes destroys the nice binomial tree structure; our trees no longer
have logarithmic depth! In fact, DECREASEKEY runs in (n) time in the worst case.
To compute the amortized cost of DECREASEKEY, well use the potential method, just as we did for
DELETEMIN. We need to nd a potential function that goes up a little whenever we do a little work,
and goes down a lot whenever we do a lot of work. DECREASEKEY unmarks several marked ancestors and
possibly also marks one node. So the number of marked nodes might be an appropriate potential function
here. Whenever we do a little bit of work, the number of marks goes up by at most one; whenever we
do a lot of work, the number of marks goes down a lot.
More precisely, let m and m
/
be the number of marked nodes before and after a DECREASEKEY
operation. The actual time (ignoring constant factors) is
t = 1 +#consecutive marked ancestors of v
and if we set = m, the increase in potential is
m
/
m 1 #consecutive marked ancestors of v.
Since t + 2, the amortized cost of DECREASEKEY is O(1) .
L.6 Bounding the Degree
But now we have a problem with our earlier analysis of DELETEMIN. The amortized time for a DELETEMIN
is still O(r +deg(min)). To show that this equaled O(log n), we used the fact that the maximum degree
of any node is O(log n), which implies that after a CLEANUP the number of roots is O(log n). But now
that we dont have complete binomial heaps, this fact is no longer obvious!
So lets prove it. For any node v, let [v[ denote the number of nodes in the subtree of v, including v
itself. Our proof uses the following lemma, which nally tells us why these things are called Fibonacci
heaps.
Lemma 1. For any node v in a Fibonacci heap, [v[ F
deg(v)+2
.
5
Algorithms Non-Lecture L: Fibonacci Heaps
Proof: Label the children of v in the chronological order in which they were linked to v. Consider the
situation just before the ith oldest child w
i
was linked to v. At that time, v had at least i 1 children
(possibly more). Since CLEANUP only links trees with the same degree, we had deg(w
i
) = deg(v) i 1.
Since that time, at most one child of w
i
has been promoted away; otherwise, w
i
would have been
promoted to the root list by now. So currently we have deg(w
i
) i 2.
We also quickly observe that deg(w
i
) 0. (Duh.)
Let s
d
be the minimum possible size of a tree with degree d in any Fibonacci heap. Clearly s
0
=1;
for notational convenience, let s
1
= 1 also. By our earlier argument, the ith oldest child of the root has
degree at least max|0, i 2|, and thus has size at least max|1, s
i2
| = s
i2
. Thus, we have the following
recurrence:
s
d
1 +
d

i=1
s
i2
If we assume inductively that s
i
F
i+2
for all 1 i < d (with the easy base cases s
1
= F
1
and
s
0
= F
2
), we have
s
d
1 +
d

i=1
F
i
= F
d+2
.
(The last step was a practice problem in Homework 0.) By denition, [v[ s
deg(v)
.
You can easily show (using either induction or the annihilator method) that F
k+2
>
k
where
=
1+
_
5
2
1.618 is the golden ratio. Thus, Lemma 1 implies that
deg(v) log

[v[ = O(log[v[).
Thus, since the size of any subtree in an n-node Fibonacci heap is obviously at most n, the degree of any
node is O(log n), which is exactly what we wanted. Our earlier analysis is still good.
L.7 Analyzing Everything Together
Unfortunately, our analyses of DELETEMIN and DECREASEKEY used two different potential functions.
Unless we can nd a single potential function that works for both operations, we cant claim both
amortized time bounds simultaneously. So we need to nd a potential function that goes up a little
during a cheap DELETEMIN or a cheap DECREASEKEY, and goes down a lot during an expensive DELETEMIN
or an expensive DECREASEKEY.
Lets look a little more carefully at the cost of each Fibonacci heap operation, and its effect on
both the number of roots and the number of marked nodes, the things we used as out earlier potential
functions. Let r and m be the numbers of roots and marks before each operation, and let r
/
and m
/
be
the numbers of roots and marks after the operation.
operation actual cost r
/
r m
/
m
INSERT 1 1 0
MERGE 1 0 0
DELETEMIN r +deg(min) r
/
r 0
DECREASEKEY 1 +m m
/
1 +m m
/
m
/
m
In particular, notice that promoting a node in DECREASEKEY requires constant time and increases the
number of roots by one, and that we promote (at most) one unmarked node.
6
Algorithms Non-Lecture L: Fibonacci Heaps
If we guess that the correct potential function is a linear combination of our old potential functions r
and m and play around with various possibilities for the coefcients, we will eventually stumble across
the correct answer:
= r +2m
To see that this potential function gives us good amortized bounds for every Fibonacci heap operation,
lets add two more columns to our table.
operation actual cost r
/
r m
/
m
/
amortized cost
INSERT 1 1 0 1 2
MERGE 1 0 0 0 1
DELETEMIN r +deg(min) r
/
r 0 r
/
r r
/
+deg(min)
DECREASEKEY 1 +m m
/
1 +m m
/
m
/
m 1 +m
/
m 2
Since Lemma 1 implies that r
/
+deg(min) = O(log n), were nally done! (Whew!)
L.8 Fibonacci Trees
To give you a little more intuition about how Fibonacci heaps behave, lets look at a worst-case
construction for Lemma 1. Suppose we want to remove as many nodes as possible from a binomial heap
of order k, by promoting various nodes to the root list, but without causing any cascading promotions.
The most damage we can do is to promote the largest subtree of every node. Call the result a Fibonacci
tree of order k +1, and denote it f
k+1
. As a base case, let f
1
be the tree with one (unmarked) node, that
is, f
1
= B
0
. The reason for shifting the index should be obvious after a few seconds.
Fibonacci trees of order 1 through 6. Light nodes have been promoted away; dark nodes are marked.
Recall that the root of a binomial tree B
k
has k children, which are roots of B
0
, B
1
, . . . , B
k1
. To
convert B
k
to f
k+1
, we promote the root of B
k1
, and recursively convert each of the other subtrees B
i
to f
i+1
. The root of the resulting tree f
k+1
has degree k 1, and the children are the roots of smaller
Fibonacci trees f
1
, f
2
, . . . , f
k1
. We can also consider B
k
as two copies of B
k1
linked together. Its quite
easy to show that an order-k Fibonacci tree consists of an order k 2 Fibonacci tree linked to an order
k 1 Fibonacci tree. (See the picture below.)
5
f
f
f
f
f
7
4
3
f
2
1
f
f
f
5
7
6
B
0 B
1
B
2
B
3
B
4
B
5
B
6
B
5
B
6
B
5
Comparing the recursive structures of B
6
and f
7
.
Since f
1
and f
2
both have exactly one node, the number of nodes in an order-k Fibonacci tree is
exactly the kth Fibonacci number! (Thats why we changed in the index.) Like binomial trees, Fibonacci
trees have lots of other nice properties that easy to prove by induction (hint, hint):
7
Algorithms Non-Lecture L: Fibonacci Heaps
The root of f
k
has degree k 2.
f
k
can be obtained from f
k1
by adding a new unmarked child to every marked node and then
marking all the old unmarked nodes.
f
k
has height |k/2 1.
f
k
has F
k2
unmarked nodes, F
k1
marked nodes, and thus F
k
nodes altogether.
f
k
has

kd2
d1

unmarked nodes,

kd2
d

marked nodes, and

kd1
d

total nodes at depth d, for

all 0 d [k/2| 1.
f
k
has F
k2h1
nodes with height h, for all 0 h [k/2| 1, and one node (the root) with height
|k/2 1.
I stopped covering Fibonacci heaps in my undergraduate algorithms class a few years ago, even
though they are a great illustration of data structure design principles and amortized analysis. My
main reason for skipping them is that the algorithms are relatively complicated, which both hinders
understanding and limits any practical advantages over regular binary heaps. (The popular algo-
rithms textbook CLRS dismisses Fibonacci heaps as predominantly of theoretical interest because of
programming complexity and large constant factors in its running time.)
Nevertheless, students interested in data structures are strongly advised to become familiar with
binomial and Fibonacci heaps, since they share key structural properties with other data structures (such
as union-nd trees and Bentley-Saxe dynamization) and illustrate important data structure techniques
(like lazy rebuilding). Also, Fibonacci heaps (and more recent extensions like Chazelles soft heaps) are
key ingredients in the fastest algorithms known for some problems.
8