Re: [algogeeks] Re: Median in stream of running integers

[atul anand]

@rahul : yes

On 3/24/13, rahul sharma  wrote:
> So we need to implement prelocate down for deletion?
>
> On Sunday, March 24, 2013, atul anand  wrote:
>> yeah implementation is wrong.
>>
>> On 3/24/13, tec  wrote:
>>> The heap implementation is wrong to only prelocate up on deletion top.
>>> 15
>>>   /\
>>>   14  13
>>>  /  \/  \
>>>1211109
>>>/\/\/\/\
>>>   8  7  6  5  4  3  2  1
>>> For example, for the above heap, when deleteTop is called, 1 is moved to
>>> top, and heaplify is called on node 9, which does nothing and leave the
>>> heap in an invalid state.
>>>
>>> Comapring l and r child to find maximum/minimum is only needed in
> prelocate
>>> down, not in prelocate up.
>>>
>>>
>>> 2013/3/24 rahul sharma 
>>>
 And also in heapify y we r not comapring l and r chid to find maximum?


 On Sun, Mar 24, 2013 at 6:07 PM, rahul sharma
 wrote:

> I was goin thorugh question on this link
>
> http://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/
> My doubt is y we uses prelocate up in case of deletion also.In
> deletion
> we use pre locate down.But y here we used pre locate up..plz
> xplain.thnx
> in
> advance
>
> // Heapification
>  // Note that, for the current median tracing problem
>  // we need to heapify only towards root, always
>  void heapify(int i)
>  {
>  int p = parent(i);
>
> // comp - differentiate MaxHeap and MinHeap
>  // percolates up
>  if( p >= 0 && comp(A[i], A[p]) )
>  {
>  Exch(A[i], A[p]);
>  heapify(p);
>  }
>  }
>
>  int deleteTop()
>  {
>  int del = -1;
>
> if( heapSize > -1)
>  {
>  del = A[0];
>
> Exch(A[0], A[heapSize]);
>  heapSize--;
>  heapify(parent(heapSize+1));
>  }
>
> return del;
>  }
>

  --
 You received this message because you are subscribed to the Google
> Groups
 "Algorithm Geeks" group.
 To unsubscribe from this group and stop receiving emails from it, send
> an
 email to algogeeks+unsubscr...@googlegroups.com.
 For more options, visit https://groups.google.com/groups/opt_out.



>>>
>>>
>>>
>>> --
>>> __
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups
>>> "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an
>>> email to algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[algogeeks] Re: Median in stream of running integers

[rahul sharma]

So we need to implement prelocate down for deletion?

On Sunday, March 24, 2013, atul anand  wrote:
> yeah implementation is wrong.
>
> On 3/24/13, tec  wrote:
>> The heap implementation is wrong to only prelocate up on deletion top.
>> 15
>>   /\
>>   14  13
>>  /  \/  \
>>1211109
>>/\/\/\/\
>>   8  7  6  5  4  3  2  1
>> For example, for the above heap, when deleteTop is called, 1 is moved to
>> top, and heaplify is called on node 9, which does nothing and leave the
>> heap in an invalid state.
>>
>> Comapring l and r child to find maximum/minimum is only needed in
prelocate
>> down, not in prelocate up.
>>
>>
>> 2013/3/24 rahul sharma 
>>
>>> And also in heapify y we r not comapring l and r chid to find maximum?
>>>
>>>
>>> On Sun, Mar 24, 2013 at 6:07 PM, rahul sharma
>>> wrote:
>>>
 I was goin thorugh question on this link

http://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/
 My doubt is y we uses prelocate up in case of deletion also.In deletion
 we use pre locate down.But y here we used pre locate up..plz
xplain.thnx
 in
 advance

 // Heapification
  // Note that, for the current median tracing problem
  // we need to heapify only towards root, always
  void heapify(int i)
  {
  int p = parent(i);

 // comp - differentiate MaxHeap and MinHeap
  // percolates up
  if( p >= 0 && comp(A[i], A[p]) )
  {
  Exch(A[i], A[p]);
  heapify(p);
  }
  }

  int deleteTop()
  {
  int del = -1;

 if( heapSize > -1)
  {
  del = A[0];

 Exch(A[0], A[heapSize]);
  heapSize--;
  heapify(parent(heapSize+1));
  }

 return del;
  }

>>>
>>>  --
>>> You received this message because you are subscribed to the Google
Groups
>>> "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
an
>>> email to algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>
>>>
>>>
>>
>>
>>
>> --
>> __
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [algogeeks] Re: Median in stream of running integers

[atul anand]

yeah implementation is wrong.

On 3/24/13, tec  wrote:
> The heap implementation is wrong to only prelocate up on deletion top.
> 15
>   /\
>   14  13
>  /  \/  \
>1211109
>/\/\/\/\
>   8  7  6  5  4  3  2  1
> For example, for the above heap, when deleteTop is called, 1 is moved to
> top, and heaplify is called on node 9, which does nothing and leave the
> heap in an invalid state.
>
> Comapring l and r child to find maximum/minimum is only needed in prelocate
> down, not in prelocate up.
>
>
> 2013/3/24 rahul sharma 
>
>> And also in heapify y we r not comapring l and r chid to find maximum?
>>
>>
>> On Sun, Mar 24, 2013 at 6:07 PM, rahul sharma
>> wrote:
>>
>>> I was goin thorugh question on this link
>>> http://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/
>>> My doubt is y we uses prelocate up in case of deletion also.In deletion
>>> we use pre locate down.But y here we used pre locate up..plz xplain.thnx
>>> in
>>> advance
>>>
>>> // Heapification
>>>  // Note that, for the current median tracing problem
>>>  // we need to heapify only towards root, always
>>>  void heapify(int i)
>>>  {
>>>  int p = parent(i);
>>>
>>> // comp - differentiate MaxHeap and MinHeap
>>>  // percolates up
>>>  if( p >= 0 && comp(A[i], A[p]) )
>>>  {
>>>  Exch(A[i], A[p]);
>>>  heapify(p);
>>>  }
>>>  }
>>>
>>>  int deleteTop()
>>>  {
>>>  int del = -1;
>>>
>>> if( heapSize > -1)
>>>  {
>>>  del = A[0];
>>>
>>> Exch(A[0], A[heapSize]);
>>>  heapSize--;
>>>  heapify(parent(heapSize+1));
>>>  }
>>>
>>> return del;
>>>  }
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>
>
> --
> __
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.