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
Report DMCA
TutorRating
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..
All Rights Reserved. Copyright by AceMyHW.com - Copyright Policy