KCS 503: Design and
Analysis of Algorithms
Fibonacci-heap
B N Pandey 8/20/2020
B N Pandey 8/20/2020
B N Pandey 8/20/2020
Fibonacci Heaps
● Like a binomial heap, a Fibonacci heap is a collection
of min-heap-ordered trees.
● The trees in a Fibonacci heap are not constrained to
be binomial trees.
● Unlike trees within binomial heaps, which are
ordered, trees within Fibonacci heaps are rooted but
unordered.
● As Figure shows, each node x contains a pointer p[x]
to its parent and a pointer child[x] to any one of its
children.
B N Pandey 8/20/2020
Cont…
● 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.
B N Pandey 8/20/2020
B N Pandey 8/20/2020
B N Pandey 8/20/2020
Potential function
● As mentioned, we shall use the potential method 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
● For example, the potential of the Fibonacci heap shown in
Figure 20.1 is 5+2 · 3 = 11. The potential of a set of Fibonacci
heaps is the sum of the potentials of its constituent Fibonacci
heaps.
B N Pandey 8/20/2020
Mergeable-heap operations
● 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 Uk consists of
two unordered binomial trees Uk−1 for which the root of one is
made into any child of the root of the other.
B N Pandey 8/20/2020
Creating a new Fibonacci heap
B N Pandey 8/20/2020
Inserting a node
B N Pandey 8/20/2020
B N Pandey 8/20/2020
Finding the minimum node
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.
B N Pandey 8/20/2020
Uniting two fibonacci heaps
B N Pandey 8/20/2020
Extracting the minimum node
B N Pandey 8/20/2020
B N Pandey 8/20/2020
B N Pandey 8/20/2020
B N Pandey 8/20/2020
B N Pandey 8/20/2020
B N Pandey 8/20/2020
B N Pandey 8/20/2020
Decreasing a key and deleting a node
B N Pandey 8/20/2020
B N Pandey 8/20/2020
B N Pandey 8/20/2020
B N Pandey 8/20/2020
Deleting a node
B N Pandey 8/20/2020
The End
B N Pandey 8/20/2020
