لطفا منتظر باشید ...
20.1 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.
Figure 20.1: (a) A Fibonacci heap consisting of five min-heap-ordered trees and 14 nodes. The dashed line indicates the root list. The minimum node of the heap is the node containing the key 3. The three marked nodes are blackened. The potential of this particular Fibonacci heap is 5+2·3 = 11. (b) A more complete representation showing pointers p (up arrows), child (down arrows), and left and right (sideways arrows). These details are omitted in the remaining figures in this chapter, since all the information shown here can be determined from what appears in part (a).
Unlike trees within binomial heaps, which are ordered, trees within Fibonacci heaps are rooted but unordered. As Section 10.2) 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. Until we look at the DECREASE-KEY operation in Section 20.3, we will just set all mark fields to FALSE.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
As mentioned, we shall use the potential method of Section 17.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
| (20.1) |  |
(We will gain some intuition for this potential function in Section 20.3.) For example, the potential of the Fibonacci heap shown in equation (17.3), an upper bound on the total amortized cost is thus an upper bound on the total actual cost for the sequence of operations.
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. Exercise 20.2-3 shows that when only the mergeable-heap operations are supported, D(n) ≤ ⌊lg n⌋. In Section 20.3, we shall show that when we support DECREASE-KEY and DELETE as well, D(n) = O(lg n).
