Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 89
Текст из файла (страница 89)
By concatenating the two arrays that hold the binaryheaps to be merged and then running MIN-HEAPIFY (see Exercise 6.2-2), the UNIONoperation takes Θ(n) time in the worst case.ProcedureMAKE-HEAPINSERTMINIMUMEXTRACT-MINUNIONDECREASEKEYDELETEBinary heap (worst- Binomial heap (worstcase)case)Fibonacci heap(amortized)Θ(1)Θ(lg n)Θ(1)Θ(lg n)Θ(n)Θ(lg n)Θ(1)O(lg n)O(lg n)Θ(lg n)O(lg n)Θ(lg n)Θ(1)Θ(1)Θ(1)O(lg n)Θ(1)Θ(1)Θ(lg n)Θ(lg n)O(lg n)Figure 19.1: Running times for operations on three implementations of mergeable heaps.
Thenumber of items in the heap(s) at the time of an operation is denoted by n.In this chapter, we examine "binomial heaps," whose worst-case time bounds are also shownin Figure 19.1. In particular, the UNION operation takes only O(lg n) time to merge twobinomial heaps with a total of n elements.In Chapter 20, we shall explore Fibonacci heaps, which have even better time bounds forsome operations. Note, however, that the running times for Fibonacci heaps in Figure 19.1 areamortized time bounds, not worst-case per-operation time bounds.This chapter ignores issues of allocating nodes prior to insertion and freeing nodes followingdeletion.
We assume that the code that calls the heap procedures deals with these details.Binary heaps, binomial heaps, and Fibonacci heaps are all inefficient in their support of theoperation SEARCH; it can take a while to find a node with a given key. For this reason,operations such as DECREASE-KEY and DELETE that refer to a given node require apointer to that node as part of their input. As in our discussion of priority queues in Section6.5, when we use a mergeable heap in an application, we often store a handle to thecorresponding application object in each mergeable-heap element, as well as a handle tocorresponding mergeable-heap element in each application object. The exact nature of thesehandles depends on the application and its implementation.Section 19.1 defines binomial heaps after first defining their constituent binomial trees.
It alsointroduces a particular representation of binomial heaps. Section 19.2 shows how we canimplement operations on binomial heaps in the time bounds given in Figure 19.1.[1]As mentioned in the introduction to Part V, our default mergeable heaps are mergeable minheaps, and so the operations MINIMUM, EXTRACT-MIN, and DECREASE-KEY apply.Alternatively, we could define a mergeable max-heap with the operations MAXIMUM,EXTRACT-MAX, and INCREASE-KEY.19.1 Binomial trees and binomial heapsA binomial heap is a collection of binomial trees, so this section starts by defining binomialtrees and proving some key properties. We then define binomial heaps and show how theycan be represented.19.1.1 Binomial treesThe binomial tree Bk is an ordered tree (see Section B.5.2) defined recursively. As shown inFigure 19.2(a), the binomial tree B0 consists of a single node.
The binomial tree Bk consists oftwo binomial trees Bk-1 that are linked together: the root of one is the leftmost child of the rootof the other. Figure 19.2(b) shows the binomial trees B0 through B4.Figure 19.2: (a) The recursive definition of the binomial tree Bk. Triangles represent rootedsubtrees. (b) The binomial trees B0 through B4. Node depths in B4 are shown. (c) Another wayof looking at the binomial tree Bk.Some properties of binomial trees are given by the following lemma.Lemma 19.1: (Properties of binomial trees)For the binomial tree Bk,1.2.3.4.there are 2k nodes,the height of the tree is k,there are exactly nodes at depth i for i = 0, 1, ..., k, andthe root has degree k, which is greater than that of any other node; moreover if i thechildren of the root are numbered from left to right by k - 1, k - 2, ..., 0, child i is theroot of a subtree Bi.Proof The proof is by induction on k. For each property, the basis is the binomial tree B0.Verifying that each property holds for B0 is trivial.For the inductive step, we assume that the lemma holds for Bk-1.1.
Binomial tree Bk consists of two copies of Bk-1, and so Bk has 2k-1 + 2k-1 = 2k nodes.2. Because of the way in which the two copies of Bk-1 are linked to form Bk, themaximum depth of a node in Bk is one greater than the maximum depth in Bk-1. By theinductive hypothesis, this maximum depth is (k - 1) + 1 = k.3. Let D(k, i) be the number of nodes at depth i of binomial tree Bk. Since Bk is composedof two copies of Bk-1 linked together, a node at depth i in Bk-1 appears in Bk once atdepth i and once at depth i + 1.
In other words, the number of nodes at depth i in Bk isthe number of nodes at depth i in Bk-1 plus the number of nodes at depth i - 1 in Bk-1.Thus,4. The only node with greater degree in Bk than in Bk-1 is the root, which has one morechild than in Bk-1.
Since the root of Bk-1 has degree k - 1, the root of Bk has degree k.Now, by the inductive hypothesis, and as Figure 19.2(c) shows, from left to right, thechildren of the root of Bk-1 are roots of Bk-2, Bk-3, ..., B0. When Bk-1 is linked to Bk-1,therefore, the children of the resulting root are roots of Bk-1, Bk-2, ..., B0.Corollary 19.2The maximum degree of any node in an n-node binomial tree is lg n.Proof Immediate from properties 1 and 4 of Lemma 19.1.The term "binomial tree" comes from property 3 of Lemma 19.1, since the termsbinomial coefficients. Exercise 19.1-3 gives further justification for the term.are the19.1.2 Binomial heapsA binomial heap H is a set of binomial trees that satisfies the following binomial-heapproperties.1.
Each binomial tree in H obeys the min-heap property: the key of a node is greaterthan or equal to the key of its parent. We say that each such tree is min-heap-ordered.2. For any nonnegative integer k, there is at most one binomial tree in H whose root hasdegree k.The first property tells us that the root of a min-heap-ordered tree contains the smallest key inthe tree.The second property implies that an n-node binomial heap H consists of at most ⌊lgn⌋ + 1binomial trees. To see why, observe that the binary representation of n has ⌊lg n⌋ + 1 bits, sayb⌊lg n⌋, b⌊lg n⌋-1, ..., b0 , so that. By property 1 of Lemma 19.1, therefore,binomial tree Bi appears in H if and only if bit bi = 1.
Thus, binomial heap H contains at most⌊lg n⌋ + 1 binomial trees.Figure 19.3(a) shows a binomial heap H with 13 nodes. The binary representation of 13 is1101 , and H consists of min-heap-ordered binomial trees B3, B2, and B0, having 8, 4, and 1nodes respectively, for a total of 13 nodes.Figure 19.3: A binomial heap H with n = 13 nodes. (a) The heap consists of binomial trees B0,B2, and B3, which have 1, 4, and 8 nodes respectively, totaling n = 13 nodes. Since eachbinomial tree is min-heap-ordered, the key of any node is no less than the key of its parent.Also shown is the root list, which is a linked list of roots in order of increasing degree.
(b) Amore detailed representation of binomial heap H . Each binomial tree is stored in the leftchild, right-sibling representation, and each node stores its degree.Representing binomial heapsAs shown in Figure 19.3(b), each binomial tree within a binomial heap is stored in the leftchild, right-sibling representation of Section 10.4. Each node has a key field and any othersatellite information required by the application. In addition, each node x contains pointersp[x] to its parent, child[x] to its leftmost child, and sibling[x] to the sibling of x immediately toits right.
If node x is a root, then p[x] = NIL. If node x has no children, then child[x] = NIL,and if x is the rightmost child of its parent, then sibling[x] = NIL. Each node x also containsthe field degree[x], which is the number of children of x.As Figure 19.3 also shows, the roots of the binomial trees within a binomial heap areorganized in a linked list, which we refer to as the root list. The degrees of the roots strictlyincrease as we traverse the root list.
By the second binomial-heap property, in an n-nodebinomial heap the degrees of the roots are a subset of {0, 1, ..., ⌊lg n⌋}. The sibling field has adifferent meaning for roots than for nonroots. If x is a root, then sibling[x] points to the nextroot in the root list.
(As usual, sibling[x] = NIL if x is the last root in the root list.)A given binomial heap H is accessed by the field head[H], which is simply a pointer to thefirst root in the root list of H . If binomial heap H has no elements, then head[H] = NIL.Exercises 19.1-1Suppose that x is a node in a binomial tree within a binomial heap, and assume that sibling[x]≠ NIL.
If x is not a root, how does degree[sibling[x]] compare to degree[x]? How about if x isa root?Exercises 19.1-2If x is a nonroot node in a binomial tree within a binomial heap, how does degree[x] compareto degree[p[x]]?Exercises 19.1-3Suppose we label the nodes of binomial tree Bk in binary by a postorder walk, as in Figure19.4. Consider a node x labeled l at depth i, and let j = k - i.
Show that x has j 1's in its binaryrepresentation. How many binary k-strings are there that contain exactly j 1's? Show that thedegree of x is equal to the number of 1's to the right of the rightmost 0 in the binaryrepresentation of l.Figure 19.4: The binomial tree B4 with nodes labeled in binary by a postorder walk.19.2 Operations on binomial heapsIn this section, we show how to perform operations on binomial heaps in the time boundsshown in Figure 19.1. We shall only show the upper bounds; the lower bounds are left asExercise 19.2-10.Creating a new binomial heapTo make an empty binomial heap, the MAKE-BINOMIAL-HEAP procedure simply allocatesand returns an object H , where head[H ] = NIL.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
