Skedbooks
←
Design Analysis of Algorithm

Mergeable-heap Operations

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)
 1 for i ← 0 to D(n[H])
 2      do A[i] ← NIL
 3 for each node w in the root list of H
 4      do x ← w
 5         d ← degree[x]
 6         while A[d] ≠ NIL
 7             do y ← A[d]      ▹ Another node with the same degree as x.
 8                if key[x] > key[y]
 9                   then exchange x ↔ y
10                FIB-HEAP-LINK(H, y, x)
11                A[d] ← NIL
12                d ← d   1
13         A[d] ← x
14 min[H] ← NIL
15 for i ← 0 to D(n[H])
16      do if A[i] ≠ NIL
17            then add A[i] to the root list of H
18                 if min[H] = NIL or key[A[i]] < key[min[H]]
19                    then min[H] ← A[i]

	FIB-HEAP-LINK(H, y, x)
1  remove y from the root list of H
2  make y a child of x, incrementing degree[x]
3  mark[y] ← FALSE

In detail, the CONSOLIDATE procedure works as follows. Lines 1-2 initialize A by making each entry NIL. The for loop of lines 3-13 processes each root w in the root list. After processing each root w, it ends up in a tree rooted at some node x, which may or may not be identical to w. Of the processed roots, no others will have the same degree as x, and so we will set array entry A[degree[x]] to point to x. When this for loop terminates, at most one root of each degree will remain, and the array A will point to each remaining root.

The while loop of lines 6-12 repeatedly links the root x of the tree containing node w to another tree whose root has the same degree as x, until no other root has the same degree. This while loop maintains the following invariant:

  • At the start of each iteration of the while loop, d = degree[x].

We use this loop invariant as follows:

  • Initialization: Line 5 ensures that the loop invariant holds the first time we enter the loop.

  • Maintenance: In each iteration of the while loop, A[d] points to some root y. Because d = degree[x] = degree[y], we want to link x and y. Whichever of x and y has the smaller key becomes the parent of the other as a result of the link operation, and so lines 8-9 exchange the pointers to x and y if necessary. Next, we link y to x by the call FIB-HEAP-LINK(H, y, x) in line 10. This call increments degree[x] but leaves degree[y] as d. Because node y is no longer a root, the pointer to it in array A is removed in line 11. Because the call of FIB-HEAP-LINK increments the value of degree[x], line 12 restores the invariant that d = degree[x].

  • Termination: We repeat the while loop until A[d] = NIL, in which case there is no other root with the same degree as x.

After the while loop terminates, we set A[d] to x in line 13 and perform the next iteration of the for loop.

Figures 20.3(c)-(e) show the array A and the resulting trees after the first three iterations of the for loop of lines 3-13. In the next iteration of the for loop, three links occur; their results are shown in Figures 20.3(f)-(h). Figures 20.3(i)-(l) show the result of the next four iterations of the for loop.

All that remains is to clean up. Once the for loop of lines 3-13 completes, line 14 empties the root list, and lines 15-19 reconstruct it from the array A. The resulting Fibonacci heap is shown in Figure 20.3(m). After consolidating the root list, FIB-HEAP-EXTRACT-MIN finishes up by decrementing n[H] in line 11 and returning a pointer to the deleted node z in line 12.

Observe that if all trees in the Fibonacci heap are unordered binomial trees before FIB-HEAP-EXTRACT-MIN is executed, then they are all unordered binomial trees afterward. There are two ways in which trees are changed. First, in lines 3-5 of FIB-HEAP-EXTRACT-MIN, each child x of root z becomes a root. Since all trees are unordered binomial trees before the link occurs, two trees whose roots each have k children must have the structure of Uk. The resulting tree therefore has the structure of Uk 1.

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 actual cost of extracting the minimum node can be accounted for as follows. An O(D(n)) contribution comes from there being at most D(n) children of the minimum node that are processed in FIB-HEAP-EXTRACT-MIN and from the work in lines 1-2 and 14-19 of CONSOLIDATE. It remains to analyze the contribution from the for loop of lines 3-13. The size of the root list upon calling CONSOLIDATE is at most D(n) t(H) - 1, since it consists of the original t(H) root-list nodes, minus the extracted root node, plus the children of the extracted node, which number at most D(n). Every time through the while loop of lines 6-12, one of the roots is linked to another, and thus the total amount of work performed in the for loop is at most proportional to D(n) t(H). Thus, the total actual work in extracting the minimum node is O(D(n) t(H)).