@atul... The only reason behind storing the indices instead of actual element values in the heap, as mentioned in my original post, was to resolve the issues that u have brought up...
Cheers :) On Jan 2, 11:08 am, Lucifer <[email protected]> wrote: > @atul.. > > There are no stability or access issues with the code.. > Below i have given explanation for ur concerns... > > -------------------------------------- > a) I think ur first concern is a stable heap... > The heap might not be stable as u have mentioned.. but the code makes > it stable.. > Hence, it won't violate the diff condition.. > > Basically ur concern is what if the max or min element that i get from > the heap is not valid for the current run (for calculating max sub - > array) > i.e. the index of max or min element is smaller that the current set > start index (currentStrtInd).. > > If you observe closely, we remove the invalid elements in the heap by > the doing the following check(as present in the code above): > *if (Top(MinH) < currentStrInd)* > pop(Top(MinH)); > > Hence, we can say as far as accessing elements of MinH and MaxH is > concerned, its always stable... > > ------------------------------------------ > > b) Your second concern is how do we ensure that if there are duplicate > elements then i should always be able to access the one with lower > index.. > > Say there is duplicate element X, having indices i and j... > (X, i) will be inserted before (X, j)... > Now there are 2 possible cases while setting the Top(MinH) i.e top > element of the heap.. > > 1) As (X, i) is inserted before (X, j) , hence (X, i) can be its > ancestor.. > Hence, while setting the top min element ( X, i) will be set as the > min as its more closer to the root. > > 2) If (X, i) in the left subtree and (X, j) is in the right > subtree.. then if X is chosen as the min value.. that means both. > Root-> left and Root-> right are X's. > Hence as both duplicates will be direct children of the root we > break the tie by picking the one with lower index.. > Basically the one with lower index has higher priority... > > On Jan 2, 8:54 am, atul anand <[email protected]> wrote: > > > > > > > > > if i am getting it right then i guess because heap is not stable i.e it > > does not guarantee that if there is multiple same elements say 4,4,4,5,5,10 > > > then doing extract min and extract max would may not give oldest index or > > you can say that 1st occurance of those multiple same elements i.e > > > arr[]= 4,4,4,5,5,5, > > index=1,2,3,4,5,6 > > > now doing extract min it may return 4 at index 3 instead of 4 at index 1. -- 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.
