suppose we simplify the Fibonacci heap idea and allow only a single tree at the top level, the one with the overall minimum element at the root. The operations are:

MakeHeap() Return an empty heap

Insert(H, x) Make x into a one-node heap X and then return Union(H, X).

Minimum(H) Return the value stored in the root of H

Extract-Min(H) The root of the tree is deleted leaving a collection of heap-

ordered trees which must be combined by pairwise Union operations

to leave a single heap-ordered tree at the top level Union(H1, H2) Make the smaller of the two roots the parent of the other root.

Decrease-Key(H, x,∆) Subtract ∆ from x. If x is not at the root of H , cut the subtree rooted at

x from it’s parent, calling it heap X, then return Union(H, X).

Delete(H, x) If x is at the root of H return Extract-Min(H); otherwise, cut the subtree rooted at

x from its parent, calling that subtree X, then return Union(H,Extract-Min(X)).

(a) Show that no matter in what order the pairwise Union operations are done, the operations

Make-Heap,Insert,Minimum,Union, and Decrease-Key take O(1) worst-case time.

(b) From the previous part, because Delete takes O(1) time plus the cost of an

Extract-Min, the performance of the data structure depends solely on the cost

of an Extract-Min. If the order of the pairwise Union operations in an Extract-Min

is uncontrolled, show there is a sequence of O(n)MakeHeap,Insert,Union, and Extract-Min

operations with amortized time Θ(n).

(c) Suppose the pairwise Union operations are done by scrambled pairing , a two-pass sweep in which on the first pass combines heaps in pairs arbitrarily, leaving half as many heaps, which are then combined arbitrarily. Prove that the amortized cost of any sequence of n

heap operations is O(√n).(Hint: Define the potential of a node with d children in an

n -node heap to be 1−min{d,√n} and the potential of the heap to be the sum of the potentials of its

nodes. What is the potential of the empty heap? Why is the potential function always non-negati

ve? What is the effect on potential of the various operations?)

(d) Show there is a sequence of O(n) MakeHeap,Insert,Union, and Extract-Min operations

with amortized time Θ(√n). (Hint: Let Hi denote a heap with a root and I children, each of

which is just a single element. Consider a heap H consisting of a root with k+k(k−1)/2 children:

k copies of H0 and one copy each of Hi, 1≤i≤k−1. Show that an Insert followed by an

Extract-Min done with an unfortunate sequence of pairings can result in a

heap with the same structure as H.)(A more subtle choice of pairing order gives O(logn) amortized cost of any sequence of n heap operations.

Subject | Computer |

Due By (Pacific Time) | 02/22/2014 05:00 pm |

Tutor | Rating |
---|---|

pallavi Chat Now! |
out of 1971 reviews More.. |

amosmm Chat Now! |
out of 766 reviews More.. |

PhyzKyd Chat Now! |
out of 1164 reviews More.. |

rajdeep77 Chat Now! |
out of 721 reviews More.. |

sctys Chat Now! |
out of 1600 reviews More.. |

sharadgreen Chat Now! |
out of 770 reviews More.. |

topnotcher Chat Now! |
out of 766 reviews More.. |

XXXIAO Chat Now! |
out of 680 reviews More.. |