@ sorurav
yes , the basic logic is required so that the code can be understood in
single Run..
i also request the same to all dear friends.....
Regards..
On Tue, Sep 28, 2010 at 8:11 PM, sourav <[email protected]> wrote:
> Hi Friends
>
> This is an interesting problem and request you all to give a brief
> intro to your code before putting the code. Or you may just mention
> the under lying concept in the code. This will be of great help and
> others will find it more ready to improve by adding there approach.
>
> Coming back to the problem an O(n) solution can exist by following the
> approach of building a min heap (or max heap) from an array of
> elements. A mean heap from an array of elements can be built by
> starting from middle element (all elements from mid +1 to end are them
> selves single element min heaps) (references available in Cormen or
> other books).
>
> During constructing the mean heap always track the min difference
> between any two elements in the so far constructed heap. At any
> instant if you are handling root 'a' which has left child l and right
> child r and aiming to build a min heap rooted at a, then the following
> cases arise
>
> 1. a is less than both l and r. In this case no movement of a is
> required. Now find |a-l| = x and |a-r| = y. 'a' cannot have a
> difference z with any element under tree rooted at l such that z < x
> becuase l is the least element in the tree rooted at l. Similarly 'a'
> cannot have a difference z' with any element under tree rooted at r
> such that z' < r. So least of x and y is the min diff between any
> elements in the so far constructed min heap rooted at 'a'.
>
> 2. a is less than l but greater than r. In this case r will replace a
> and a need to be pushed down the its right child. While pushing 'a'
> down keep calculating the differences between 'a' and 'r' as long as
> 'a' is not pushed down to a node where it is the min element. While
> you keep calculating also keep track of the min diff calculated so far
> (say 'p'). Compare this 'p' with |a-l| and min diff between any two
> elements for the tree rooted at l. Least of these three will be the
> min diff between any 2 elements for the min head rooted at 'r' (which
> replaced 'a''s position.
>
> 3. Both 'l' and 'r' are less than 'a'. Take the lesser or 'l' and 'r'
> and replace that with 'a' and push 'a' down as in case 2 (normal min
> heap construction algo).
>
> Thus we can continue building the min heap and at the end have the min
> diff between any 2 elements in the array. Just we keep tracking the
> min diff, we can also keep note of the 2 elements than are
> contributing to this min diff my adding some more steps.
>
> This idea is all based on the fact that min heap can be constructed
> from an array in linear time.
>
> Thanks,
> Sourav
>
>
> On Sep 27, 1:32 pm, rahul <[email protected]> wrote:
> > If their is no constrain on assumptions.
> >
> > 1.Sort the array.
> > 2. check the dif between 2 elements.
> >
> > { 99,35,45,33,88,9098,112,33455,678,3}
> >
> > sorted arrary : { } would be something.
> > now update the min_diff.
> >
> > another example : { 7,8,1,3,5,4}
> > sorted arrary : { 1,3,4,5,7,8}
> > min diff is 1.
> >
> > Please correct me if i missed something.
> >
> > On Mon, Sep 27, 2010 at 1:13 PM, satish <[email protected]> wrote:
> > > step1>construct heap using siftdown. // time complexity wil be O(n)
> and
> > > space complexity O(1).
> > > step2>take mindifference=a[1].
> > > step3>for i=1 ,i<=n/2 do
> > > { find the difference of
> (root,root-left),(root,root->right)and
> > > (root->left,root->right).and maintain mindifference is the smallest
> > > difference of among
> > > three differences.
> > > }
> > > step4>return mindifference.
> >
> > > plz correct me if im wrong....
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected]<algogeeks%[email protected]>
> <algogeeks%[email protected]<algogeeks%[email protected]>
> >
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
*Divesh*
(¨`·.·´¨) Always
`·.¸(¨`·.·´¨ ) Keep
(¨`·.·´¨)¸.·´Smiling!
`·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's
of reasons 2Smile"
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
