Please prove ths by standard methods. Let B be the binary representation of the

Question

Please prove ths by standard methods.

Let B be the binary representation of the number of elements in a binomial heap. Consider inserting a node in the heap. Prove that, the number of times two trees in the binomial heap are merged into a bigger tree is equal to the number of bit- ips when B is incremented by 1.

and

Consider two binomial heaps H1 and H2, and let the binary representation of the number of
elements in the two heaps, be B1 and B2 respectively. Prove that while merging H1 and H2,
the number of times two smaller trees are merged into a bigger tree, is equal to the number of
carry-overs generated when B1 and B2 are added.

Explanation / Answer

MAKE-HEAP() creates and returns a new heap containing no elements. INSERT(H, x) inserts node x, whose key field has already been filled in, into heap H. MINIMUM(H) returns a pointer to the node in heap H whose key is minimum. EXTRACT-MIN(H) deletes the node from heap H whose key is minimum, returning a pointer to the node. UNION(H1, H2) creates and returns a new heap that contains all the nodes of heaps H1 and H2. Heaps H1 and H2 are “destroyed” by this operation. In addition, the data structures in these chapters also support the following two operations. DECREASE-KEY(H, x, k) assigns to node x within heap H the new key value k, which is assumed to be no greater than its current key value.1 DELETE(H, x) deletes node x from heap H. As the table in Figure 19.1 shows, if we don’t need the UNION operation, ordinary binary heaps, as used in heapsort (Chapter 6), work well. Operations other than UNION run in worst-case time O(lg n) on a binary heap. If the UNION operation must be supported, however, binary heaps perform poorly. By concatenating the two arrays that hold the binary heaps to be merged and then running MIN-HEAPIFY

Binomial trees The binomial tree Bk is an ordered tree defined recursively. As , the binomial tree B0 consists of a single node. The binomial tree Bk consists of two binomial trees Bk1 that are linked together: the root of one is the leftmost child of the root of the other. the binomial trees B0 through B4. Some properties of binomial trees are given by the following lemma.

1. there are 2k nodes, 2. the height of the tree is k, 3. there are exactly k i nodes at depth i for i = 0, 1, . . . , k, and 4. the root has degree k, which is greater than that of any other node; moreover if the children of the root are numbered from left to right by k 1, k 2, . . . , 0, child i is the root 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 Bk1. 1. Binomial tree Bk consists of two copies of Bk1, and so Bk has 2k1+2 k1 = 2 k nodes. 2. Because of the way in which the two copies of Bk1 are linked to form Bk, the maximum depth of a node in Bk is one greater than the maximum depth in Bk1. By the inductive 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 composed of two copies of Bk1 linked together, a node at depth i in Bk1 appears in Bk once at depth i and once at depth i + 1. In other words, the number of nodes at depth i in Bk is the number of nodes at depth i in Bk1 plus

A binomial heap H is a set of binomial trees that satisfies the following binomialheap properties. 1. Each binomial tree in H obeys the min-heap property: the key of a node is greater than 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 has degree k. The first property tells us that the root of a min-heap-ordered tree contains the smallest key in the tree. The second property implies that an n-node binomial heap H consists of at most lg n + 1 binomial trees. To see why, observe that the binary representation of n has lg n + 1 bits, say hblg n, blg n1, . . . , b0i, so that n = Plg n i=0 bi2 i . 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 is h1101i, and H consists of min-heap-ordered binomial trees B3, B2, and B0, having 8, 4, and 1 nodes respectively, for a total of 13 nodes.

Finding the minimum key The procedure BINOMIAL-HEAP-MINIMUM returns a pointer to the node with the minimum key in an n-node binomial heap H. This implementation assumes that there are no keys with value . (See Exercise 19.2-5.) BINOMIAL-HEAP-MINIMUM(H) 1 y NIL 2 x head[H] 3 min 4 while x 6= NIL 5 do if key[x] < min 6 then min key[x] 7 y x 8 x sibling[x] 9 return y Since a binomial heap is min-heap-ordered, the minimum key must reside in a root node. The BINOMIAL-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.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.