Overview of Fibonacci Heaps: In Binomial heaps, 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.
Structure of 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, however. Figure 20.1(a) shows an example of a Fibonacci heap.
Unlike trees within binomial heaps, which are ordered, trees within Fibonacci heaps are rooted but unordered. As Figure 20.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.
Circular, doubly linked lists have two advantages for use in Fibonacci heaps. First, we can remove a node from a circular, doubly linked list in O(1) time. Second, given two such lists, we can concatenate them (or "splice" them together) into one circular, doubly linked list in O(1) time. In the descriptions of Fibonacci heap operations, we shall refer to these operations informally, letting the reader fill in the details of their implementations.
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 has lost a child since the last time x was made the child of another node. 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 a tree containing a minimum key; this node is called the minimum node of the Fibonacci heap. If a Fibonacci heap H is empty, then min[H] = NIL.
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 min[H] thus points to the node in the root list whose key is minimum. The order of the trees within a root list is arbitrary.
We rely on one other attribute for a Fibonacci heap H: the number of nodes currently in H is kept in n[H].
Potential function: 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. We shall assume that a unit of potential can pay for a constant amount of work, where the constant is sufficiently large to cover the cost of any of the specific constant-time pieces of work that we might encounter.
We assume that a Fibonacci heap application begins with no heaps. The initial potential, therefore, is 0, and by equation (20.1), the potential is nonnegative at all subsequent times.
Maximum degree
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 node in an n-node Fibonacci heap.