No Title

CSE 5311 Fall 1999

Quiz #7

1.

(10 points.) Prove the following property of binomial trees: for binomial tree B_k, the root has degree k, and the children of the root from left to right are binomial trees $B_{k-1}, \;B_{k-2},\; \ldots, \;B_0$ .

See proof in lecture notes.

2.

(10 points.) Show the Fibonacci Heap that results from each of the following operations: Insert(7), Insert(8), Insert(3), Insert(2), Insert(15), ExtractMin, Insert(10), Delete(15), ExtractMin

Insert(7)
    min
-----7------

Insert(8)
       min
----8---7----

Insert(3)
   min
----3----8---7--

Insert(2)
   min
----2---3---8---7--

Insert(15)
       min
--15----2---3---8---7--

ExtractMin
     min
------3------
     /|
    7 8
    |
   15

Insert(10)
     min
--10--3------
     /|
    7 8
    |
   15

Delete(15)
     min
--10--3------
     /|
   7* 8
   * = marked node

ExtractMin
           min
-----10-----7-----
            |
            8