Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 90
Текст из файла (страница 90)
The running time is Θ(1).Finding the minimum keyThe procedure BINOMIAL-HEAP-MINIMUM returns a pointer to the node with theminimum key in an n-node binomial heap H. This implementation assumes that there are nokeys with value ∞. (See Exercise 19.2-5.)BINOMIAL-HEAP-MINIMUM(H)1 y ← NIL2 x ← head[H]3 min ← ∞4 while x ≠ NIL5do if key[x] < min6then min ← key[x]7y ← x8x ← sibling[x]9 return ySince a binomial heap is min-heap-ordered, the minimum key must reside in a root node.
TheBINOMIAL-HEAP-MINIMUM procedure checks all roots, which number at most⌊lg n⌋ + 1,saving the current minimum in min and a pointer to the current minimum in y. When called onthe binomial heap of Figure 19.3, BINOMIAL-HEAP-MINIMUM returns a pointer to thenode with key 1.Because there are at most ⌊lg n⌋ + 1 roots to check, the running time of BINOMIAL-HEAPMINIMUM is O(lg n).Uniting two binomial heapsThe operation of uniting two binomial heaps is used as a subroutine by most of the remainingoperations. The BINOMIAL-HEAP-UNION procedure repeatedly links binomial trees whoseroots have the same degree. The following procedure links the Bk-1 tree rooted at node y to theBk-1 tree rooted at node z; that is, it makes z the parent of y.
Node z thus becomes the root of aBk tree.BINOMIAL-LINK(y, z)1 p[y] ← z2 sibling[y] ← child[z]3 child[z] ← y4 degree[z] ← degree[z] + 1The BINOMIAL-LINK procedure makes node y the new head of the linked list of node z'schildren in O(1) time. It works because the left-child, right-sibling representation of eachbinomial tree matches the ordering property of the tree: in a Bk tree, the leftmost child of theroot is the root of a Bk-1 tree.The following procedure unites binomial heaps H1 and H2, returning the resulting heap. Itdestroys the representations of H1 and H2 in the process.
Besides BINOMIAL-LINK, theprocedure uses an auxiliary procedure BINOMIAL-HEAP-MERGE that merges the root listsof H1 and H2 into a single linked list that is sorted by degree into monotonically increasingorder. The BINOMIAL-HEAP-MERGE procedure, whose pseudocode we leave as Exercise19.2-1, is similar to the MERGE procedure in Section 2.3.1.BINOMIAL-HEAP-UNION(H1, H2)1 H ← MAKE-BINOMIAL-HEAP()2 head[H] ← BINOMIAL-HEAP-MERGE(H1, H2)3 free the objects H1 and H2 but not the lists they point to4 if head[H] = NIL5then return H6 prev-x ← NIL7 x ← head[H]8 next-x ← sibling[x]9 while next-x ≠ NIL10do if (degree[x] ≠ degree[next-x]) or(sibling[next-x] ≠ NIL and degree[sibling[next-x]] =degree[x])112then prev-x ← x▹ Cases 1 and12213x ← next-x▹ Cases 1 andelse if key[x] ≤ key[next-x]14then sibling[x] ← sibling[next-x]15BINOMIAL-LINK(next-x, x)16else if prev-x = NIL17then head[H] ← next-x18else sibling[prev-x] ← next-x19202122BINOMIAL-LINK(x, next-x)x ← next-xnext-x ← sibling[x]return H▹ Case 3▹ Case 3▹ Case 4▹ Case 4▹ Case 4▹ Case 4▹ Case 4Figure 19.5 shows an example of BINOMIAL-HEAP-UNION in which all four cases given inthe pseudocode occur.Figure 19.5: The execution of BINOMIAL-HEAP-UNION.
(a) Binomial heaps H1 and H2. (b)Binomial heap H is the output of BINOMIAL-HEAP-MERGE(H1, H2). Initially, x is the firstroot on the root list of H . Because both x and next-x have degree 0 and key[x] < key[next-x],case 3 applies. (c) After the link occurs, x is the first of three roots with the same degree, socase 2 applies. (d) After all the pointers move down one position in the root list, case 4applies, since x is the first of two roots of equal degree.
(e) After the link occurs, case 3applies. (f) After another link, case 1 applies, because x has degree 3 and next-x has degree 4.This iteration of the while loop is the last, because after the pointers move down one positionin the root list, next-x = NIL.The BINOMIAL-HEAP-UNION procedure has two phases. The first phase, performed by thecall of BINOMIAL-HEAP-MERGE, merges the root lists of binomial heaps H1 and H2 into asingle linked list H that is sorted by degree into monotonically increasing order. There mightbe as many as two roots (but no more) of each degree, however, so the second phase linksroots of equal degree until at most one root remains of each degree.
Because the linked list His sorted by degree, we can perform all the link operations quickly.In detail, the procedure works as follows. Lines 1-3 start by merging the root lists of binomialheaps H1 and H2 into a single root list H . The root lists of H1 and H2 are sorted by strictlyincreasing degree, and BINOMIAL-HEAP-MERGE returns a root list H that is sorted bymonotonically increasing degree. If the root lists of H1 and H2 have m roots altogether,BINOMIAL-HEAP-MERGE runs in O(m) time by repeatedly examining the roots at theheads of the two root lists and appending the root with the lower degree to the output root list,removing it from its input root list in the process.The BINOMIAL-HEAP-UNION procedure next initializes some pointers into the root list ofH .
First, it simply returns in lines 4-5 if it happens to be uniting two empty binomial heaps.From line 6 on, therefore, we know that H has at least one root. Throughout the procedure, wemaintain three pointers into the root list:•••x points to the root currently being examined,prev-x points to the root preceding x on the root list: sibling[prev-x] = x (since initiallyx has no predecessor, we start with prev-x set to NIL), andnext-x points to the root following x on the root list: sibling[x] = next-x.Initially, there are at most two roots on the root list H of a given degree: because H1 and H2were binomial heaps, they each had at most one root of a given degree. Moreover,BINOMIAL-HEAP-MERGE guarantees us that if two roots in H have the same degree, theyare adjacent in the root list.In fact, during the execution of BINOMIAL-HEAP-UNION, there may be three roots of agiven degree appearing on the root list H at some time.
We shall see in a moment how thissituation could occur. At each iteration of the while loop of lines 9-21, therefore, we decidewhether to link x and next-x based on their degrees and possibly the degree of sibling[next-x].An invariant of the loop is that each time we start the body of the loop, both x and next-x arenon-NIL. (See Exercise 19.2-4 for a precise loop invariant.)Case 1, shown in Figure 19.6(a), occurs when degree[x] ≠ degree[next-x], that is, when x isthe root of a Bk-tree and next-x is the root of a Bl-tree for some l > k.
Lines 11-12 handle thiscase. We don't link x and next-x, so we simply march the pointers one position farther downthe list. Updating next-x to point to the node following the new node x is handled in line 21,which is common to every case.Figure 19.6: The four cases that occur in BINOMIAL-HEAP-UNION. Labels a, b, c, and dserve only to identify the roots involved; they do not indicate the degrees or keys of theseroots.
In each case, x is the root of a Bk-tree and l > k. (a) Case 1: degree[x] ≠ degree[next-x].The pointers move one position farther down the root list. (b) Case 2: degree[x] =degree[next-x] = degree[sibling[next-x]]. Again, the pointers move one position farther downthe list, and the next iteration executes either case 3 or case 4. (c) Case 3: degree[x] =degree[next-x] ≠ degree[sibling[next-x]] and key[x] ≤ key[next-x].
We remove next-x from theroot list and link it to x, creating a Bk+1-tree. (d) Case 4: degree[x] = degree[next-x] ≠degree[sibling[next-x]] and key[next-x] ≤ key[x]. We remove x from the root list and link it tonext-x, again creating a Bk+1-tree.Case 2, shown in Figure 19.6(b), occurs when x is the first of three roots of equal degree, thatis, whendegree[x] = degree[next-x] = degree[sibling[next-x]].We handle this case in the same manner as case 1: we just march the pointers one positionfarther down the list.
The next iteration will execute either case 3 or case 4 to combine thesecond and third of the three equal-degree roots. Line 10 tests for both cases 1 and 2, and lines11-12 handle both cases.Cases 3 and 4 occur when x is the first of two roots of equal degree, that is, whendegree[x] = degree[next-x] ≠ degree[sibling[next-x]].These cases may occur in any iteration, but one of them always occurs immediately followingcase 2.
In cases 3 and 4, we link x and next-x. The two cases are distinguished by whether x ornext-x has the smaller key, which determines the node that will be the root after the two arelinked.In case 3, shown in Figure 19.6(c), key[x] ≤ key[next-x], so next-x is linked to x. Line 14removes next-x from the root list, and line 15 makes next-x the leftmost child of x.In case 4, shown in Figure 19.6(d), next-x has the smaller key, so x is linked to next-x.
Lines16-18 remove x from the root list; there are two cases depending on whether x is the first rooton the list (line 17) or is not (line 18). Line 19 then makes x the leftmost child of next-x, andline 20 updates x for the next iteration.Following either case 3 or case 4, the setup for the next iteration of the while loop is the same.We have just linked two Bk-trees to form a Bk+1-tree, which x now points to. There werealready zero, one, or two other Bk+1-trees on the root list resulting from BINOMIAL-HEAPMERGE, so x is now the first of either one, two, or three Bk+1-trees on the root list. If x is theonly one, then we enter case 1 in the next iteration: degree[x] ≠ degree[next-x].
If x is the firstof two, then we enter either case 3 or case 4 in the next iteration. It is when x is the first ofthree that we enter case 2 in the next iteration.The running time of BINOMIAL-HEAP-UNION is O(lg n), where n is the total number ofnodes in binomial heaps H1 and H2. We can see this as follows. Let H1 contain n1 nodes andH2 contain n2 nodes, so that n = n1 + n2. Then H1 contains at most ⌊lg n1⌋+1 roots and H2contains at most ⌊lg n2⌋+1 roots, and so H contains at most ⌊lg n1⌋+⌊lg n2⌋+2 ≤ 2⌊lg n⌋+2 =O(lg n) roots immediately after the call of BINOMIAL-HEAP-MERGE. The time to performBINOMIAL-HEAP-MERGE is thus O(lg n).
Each iteration of the while loop takes O(1) time,and there are at most ⌊lg n1⌋ + ⌊lgn2⌋ + 2 iterations because each iteration either advances thepointers one position down the root list of H or removes a root from the root list. The totaltime is thus O(lg n).Inserting a nodeThe following procedure inserts node x into binomial heap H , assuming that x has alreadybeen allocated and key[x] has already been filled in.BINOMIAL-HEAP-INSERT(H, x)1 H′ ← MAKE-BINOMIAL-HEAP()2 p[x] ← NIL3 child[x] ← NIL4 sibling[x] ← NIL5 degree[x] ← 06 head[H′] ← x7 H ← BINOMIAL-HEAP-UNION(H, H′)The procedure simply makes a one-node binomial heap H′ in O(1) time and unites it with then-node binomial heap H in O(lg n) time.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
