Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 91
Текст из файла (страница 91)
The call to BINOMIAL-HEAP-UNION takes care offreeing the temporary binomial heap H′. (A direct implementation that does not callBINOMIAL-HEAP-UNION is given as Exercise 19.2-8.)Extracting the node with minimum keyThe following procedure extracts the node with the minimum key from binomial heap H andreturns a pointer to the extracted node.BINOMIAL-HEAP-EXTRACT-MIN(H)1 find the root x with the minimum key in the root list of H,and remove x from the root list of H2 H′ ← MAKE-BINOMIAL-HEAP()3 reverse the order of the linked list of x's children,and set head[H′] to point to the head of the resulting list4 H ← BINOMIAL-HEAP-UNION(H, H′)5 return xThis procedure works as shown in Figure 19.7.
The input binomial heap H is shown in Figure19.7(a). Figure 19.7(b) shows the situation after line 1: the root x with the minimum key hasbeen removed from the root list of H . If x is the root of a Bk-tree, then by property 4 ofLemma 19.1, x's children, from left to right, are roots of Bk-1-, Bk-2-, ..., B0-trees. Figure19.7(c) shows that by reversing the list of x's children in line 3, we have a binomial heap H′that contains every node in x's tree except for x itself.
Because x's tree was removed from H inline 1, the binomial heap that results from uniting H and H′ in line 4, shown in Figure 19.7(d),contains all the nodes originally in H except for x. Finally, line 5 returns x.Figure 19.7: The action of BINOMIAL-HEAP-EXTRACT-MIN.
(a) A binomial heap H. (b)The root x with minimum key is removed from the root list of H . (c) The linked list of x'schildren is reversed, giving another binomial heap H′. (d) The result of uniting H and H'.Since each of lines 1-4 takes O(lg n) time if H has n nodes, BINOMIAL-HEAP-EXTRACTMIN runs in O(lg n) time.Decreasing a keyThe following procedure decreases the key of a node x in a binomial heap H to a new value k.It signals an error if k is greater than x's current key.BINOMIAL-HEAP-DECREASE-KEY(H, x, k)1 if k > key[x]2then error "new key is greater than current key"3 key[x] ← k4 y ← x5 z ← p[y]6 while z ≠ NIL and key[y] < key[z]7do exchange key[y] ↔ key[z]8910▸ If y and z have satellite fields, exchange them, too.y ← zz ← p[y]As shown in Figure 19.8, this procedure decreases a key in the same manner as in a binarymin-heap: by "bubbling up" the key in the heap.
After ensuring that the new key is in fact nogreater than the current key and then assigning the new key to x, the procedure goes up thetree, with y initially pointing to node x. In each iteration of the while loop of lines 6-10, key[y]is checked against the key of y's parent z.
If y is the root or key[y] ≥ key[z], the binomial tree isnow min-heap-ordered. Otherwise, node y violates min-heap ordering, and so its key isexchanged with the key of its parent z, along with any other satellite information. Theprocedure then sets y to z, going up one level in the tree, and continues with the next iteration.Figure 19.8: The action of BINOMIAL-HEAP-DECREASE-KEY. (a) The situation justbefore line 6 of the first iteration of the while loop. Node y has had its key decreased to 7,which is less than the key of y's parent z. (b) The keys of the two nodes are exchanged, andthe situation just before line 6 of the second iteration is shown. Pointers y and z have movedup one level in the tree, but min-heap order is still violated.
(c) After another exchange andmoving pointers y and z up one more level, we find that min-heap order is satisfied, so thewhile loop terminates.The BINOMIAL-HEAP-DECREASE-KEY procedure takes O(lg n) time. By property 2 ofLemma 19.1, the maximum depth of x is ⌊lg n⌋, so the while loop of lines 6-10 iterates atmost ⌊lg n⌋ times.Deleting a keyIt is easy to delete a node x's key and satellite information from binomial heap H in O(lg n)time. The following implementation assumes that no node currently in the binomial heap hasa key of -∞.BINOMIAL-HEAP-DELETE(H, x)1 BINOMIAL-HEAP-DECREASE-KEY(H, x, -∞)2 BINOMIAL-HEAP-EXTRACT-MIN(H)The BINOMIAL-HEAP-DELETE procedure makes node x have the unique minimum key inthe entire binomial heap by giving it a key of -∞.
(Exercise 19.2-6 deals with the situation inwhich -∞ cannot appear as a key, even temporarily.) It then bubbles this key and theassociated satellite information up to a root by calling BINOMIAL-HEAP-DECREASEKEY. This root is then removed from H by a call of BINOMIAL-HEAP-EXTRACT-MIN.The BINOMIAL-HEAP-DELETE procedure takes O(lg n) time.Exercises 19.2-1Write pseudocode for BINOMIAL-HEAP-MERGE.Exercises 19.2-2Show the binomial heap that results when a node with key 24 is inserted into the binomialheap shown in Figure 19.7(d).Exercises 19.2-3Show the binomial heap that results when the node with key 28 is deleted from the binomialheap shown in Figure 19.8(c).Exercises 19.2-4Argue the correctness of BINOMIAL-HEAP-UNION using the following loop invariant:••At the start of each iteration of the while loop of lines 9-21, x points to a root that isone of the following:o the only root of its degree,o the first of the only two roots of its degree, oro the first or second of the only three roots of its degree.Moreover, all roots preceding x's predecessor on the root list have unique degrees onthe root list, and if x's predecessor has a degree different from that of x, its degree onthe root list is unique, too.
Finally, node degrees monotonically increase as we traversethe root list.Exercises 19.2-5Explain why the BINOMIAL-HEAP-MINIMUM procedure might not work correctly if keyscan have the value ∞. Rewrite the pseudocode to make it work correctly in such cases.Exercises 19.2-6Suppose there is no way to represent the key -∞.
Rewrite the BINOMIAL-HEAP-DELETEprocedure to work correctly in this situation. It should still take O(lg n) time.Exercises 19.2-7Discuss the relationship between inserting into a binomial heap and incrementing a binarynumber and the relationship between uniting two binomial heaps and adding two binarynumbers.Exercises 19.2-8In light of Exercise 19.2-7, rewrite BINOMIAL-HEAP-INSERT to insert a node directly intoa binomial heap without calling BINOMIAL-HEAP-UNION.Exercises 19.2-9Show that if root lists are kept in strictly decreasing order by degree (instead of strictlyincreasing order), each of the binomial heap operations can be implemented without changingits asymptotic running time.Exercises 19.2-10Find inputs that cause BINOMIAL-HEAP-EXTRACT-MIN, BINOMIAL-HEAPDECREASE-KEY, and BINOMIAL-HEAP-DELETE to run in Ω(lg n) time. Explain why theworst-case running times of BINOMIAL-HEAP-INSERT, BINOMIAL-HEAP-MINIMUM,but not Ω(lg n).
(See Problem 3-5.)and BINOMIAL-HEAP-UNION areProblems 19-1: 2-3-4 heapsChapter 18 introduced the 2-3-4 tree, in which every internal node (other than possibly theroot) has two, three, or four children and all leaves have the same depth. In this problem, weshall implement 2-3-4 heaps, which support the mergeable-heap operations.The 2-3-4 heaps differ from 2-3-4 trees in the following ways. In 2-3-4 heaps, only leavesstore keys, and each leaf x stores exactly one key in the field key[x]. There is no particularordering of the keys in the leaves; that is, from left to right, the keys may be in any order.Each internal node x contains a value small[x] that is equal to the smallest key stored in anyleaf in the subtree rooted at x. The root r contains a field height[r] that is the height of the tree.Finally, 2-3-4 heaps are intended to be kept in main memory, so that disk reads and writes arenot needed.Implement the following 2-3-4 heap operations.
Each of the operations in parts (a)-(e) shouldrun in O(lg n) time on a 2-3-4 heap with n elements. The UNION operation in part (f) shouldrun in O(lg n) time, where n is the number of elements in the two input heaps.a. MINIMUM, which returns a pointer to the leaf with the smallest key.b. DECREASE-KEY, which decreases the key of a given leaf x to a given value k ≤key[x].c. INSERT, which inserts leaf x with key k.d. DELETE, which deletes a given leaf x.e. EXTRACT-MIN, which extracts the leaf with the smallest key.f. UNION, which unites two 2-3-4 heaps, returning a single 2-3-4 heap and de-stroyingthe input heaps.Problems 19-2: Minimum-spanning-tree algorithm using binomial heapsChapter 23 presents two algorithms to solve the problem of finding a minimum spanning treeof an undirected graph.
Here, we shall see how binomial heaps can be used to devise adifferent minimum-spanning-tree algorithm.We are given a connected, undirected graph G = (V, E) with a weight function w : E → R. Wecall w(u, v) the weight of edge (u, v). We wish to find a minimum spanning tree for G: anacyclic subset T E that connects all the vertices in V and whose total weightis minimized.The following pseudocode, which can be proven correct using techniques from Section 23.1,constructs a minimum spanning tree T . It maintains a partition {Vi} of the vertices of V and,with each set Vi, a setEi(u, v): uVi or vVi}of edges incident on vertices in VI.MST(G)1 T ← Ø2 for each vertex viV[G]3do Vi ← {vi}4Ei ← {(vi, v)E[G]}5 while there is more than one set Vi6do choose any set Vi7extract the minimum-weight edge (u, v) from Ei8assume without loss of generality that uVi and v9if i ≠ jVj101112then T ← TVi ← ViEi ← Ei{(u, v)}Vj, destroying VjEjDescribe how to implement this algorithm using binomial heaps to manage the vertex andedge sets.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
