@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.
