@Lucifier :
i was considering algo as mentioned by you and was considering heap with
indexes as mentioned in your first post i.e :-
/*
Also, though the MinH and MaxH is designed based on the element values
i.e A[i], but we will store only the index of the element i.e. 'i'.
// The above app will work as given the index we can always retrieve
the actual value i.e. A[i]..
*/
i guess i wrote it wrongly , but was considering it as mentioned by you.
it would be great if we discuss on the given sequence instead of
considering different one.
let considering below example
please check it and comment if i am doing it wrong.
INPUT
6
10
8
5
9
7
1
4
INDEX
0
1
2
3
4
5
6
7
K=8;
Heap formed so far , when j reaches at index position j=6
Min_heap formed (containing indexed of the elements)
6
3
0
5
2
4
1
Max_Heap formed(containing indexed of the elements)
1
4
2
5
0
3
6
A[Top(MaxH)] - A[Top(MinH)] > K // (A[1] - A[6] > 8)
//we are in else part of your logic
A[j] = A[Top(MinH)]; // A[6]==A[Top(MinH)] where
j=6 and Top(MinH)=6
currentStrInd = Top(MaxH) +1; // currentStrInd= 1+1 = 2 where
Top(MaxH) = 1
pop(Top(MaxH)); // removing index 1 from MaxH
so new MaxH will be :-
4
2
5
0
3
6
while(MaxH is not empty)
{
if (Top(MaxH) < currentStrInd) // 4 < 2 here Top(MaxH) = 4 and
currentStrInd=2
// condition fail
move to else if
pop(Top(MaxH)) ; // *no pop operation taking place bcozz
condition fails*
else if (A[Top(MaxH)] - A[Top(MinH)] <= K) // A[4] - A[6] <= K i.e (9
- 1 <=8 )
//
here Top(MaxH)=4 and Top(MinH)=1
break; //* condition satisfy so break this loop*
}
Heap after loop breaks:-
Min_heap
6
3
0
5
2
4
1
Max_heap
4
2
5
0
3
6
please check this example and let me know where i am getting it wrong.
thanks
--
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.
