Skip to content

Latest commit

 

History

History
83 lines (56 loc) · 2.97 KB

19.2.md

File metadata and controls

83 lines (56 loc) · 2.97 KB
Raw

Exercises 19.2-1

Write pseudocode for BINOMIAL-HEAP-MERGE.

Answer

implementation

Exercises 19.2-2

Show the binomial heap that results when a node with key 24 is inserted into the binomial heap shown in Figure 19.7(d).

Answer

straightforward

Exercises 19.2-3

Show the binomial heap that results when the node with key 28 is deleted from the binomial heap shown in Figure 19.8(c).

Answer

straightforward

Exercises 19.2-4

Argue 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 is one of the following:

  1. the only root of its degree,
  2. the first of the only two roots of its degree, or
  3. 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 on the root list, and if x's predecessor has a degree different from that of x, its degree on the root list is unique, too. Finally, node degrees monotonically increase as we traverse the root list.

Answer

straightforward

Exercises 19.2-5

Explain why the BINOMIAL-HEAP-MINIMUM procedure might not work correctly if keys can have the value ∞. Rewrite the pseudocode to make it work correctly in such cases.

Answer

If keys can have the value ∞, then the initial value of min can not compare with that.

So we could set min to the first value of binomial heap by default.

Exercises 19.2-6

Suppose there is no way to represent the key -∞. Rewrite the BINOMIAL-HEAP-DELETE procedure to work correctly in this situation. It should still take O(lg n) time.

Answer

Exercises 19.2-7

Discuss the relationship between inserting into a binomial heap and incrementing a binary number and the relationship between uniting two binomial heaps and adding two binary numbers.

Answer

It's similar, first we add one '1', if the original number in the position is '1' too, then we carry '1' to preceeding bit.

Exercises 19.2-8

In light of Exercise 19.2-7, rewrite BINOMIAL-HEAP-INSERT to insert a node directly into a binomial heap without calling BINOMIAL-HEAP-UNION.

Answer

straightforward.

just do "addtion"

Exercises 19.2-9

Show that if root lists are kept in strictly decreasing order by degree (instead of strictly increasing order), each of the binomial heap operations can be implemented without changing its asymptotic running time.

Answer

Exercises 19.2-10

Find inputs that cause BINOMIAL-HEAP-EXTRACT-MIN, BINOMIAL-HEAP- DECREASE-KEY, and BINOMIAL-HEAP-DELETE to run in Ω(lg n) time. Explain why the worst-case running times of BINOMIAL-HEAP-INSERT, BINOMIAL-HEAP-MINIMUM, and BINOMIAL-HEAP-UNION are  but not Ω(lg n). (See Problem 3-5.)

Answer

Follow @louis1992 on github to help finish this task.