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

Chat Now!

out of 1971 reviews

Chat Now!

out of 766 reviews

Chat Now!

out of 1164 reviews

Chat Now!

out of 721 reviews

Chat Now!

out of 1600 reviews

Chat Now!

out of 770 reviews

Chat Now!

out of 766 reviews

Chat Now!

out of 680 reviews
All Rights Reserved. Copyright by - Copyright Policy