# Project #23351 - algorithm

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 1min{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(k1)/2 children:

k copies of H0 and one copy each of Hi, 1ik1. 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
TutorRating
pallavi

Chat Now!

out of 1971 reviews
amosmm

Chat Now!

out of 766 reviews
PhyzKyd

Chat Now!

out of 1164 reviews
rajdeep77

Chat Now!

out of 721 reviews
sctys

Chat Now!

out of 1600 reviews

Chat Now!

out of 770 reviews
topnotcher

Chat Now!

out of 766 reviews
XXXIAO

Chat Now!

out of 680 reviews