@rahul : yes On 3/24/13, rahul sharma <[email protected]> wrote: > So we need to implement prelocate down for deletion? > > On Sunday, March 24, 2013, atul anand <[email protected]> wrote: >> yeah implementation is wrong. >> >> On 3/24/13, tec <[email protected]> wrote: >>> The heap implementation is wrong to only prelocate up on deletion top. >>> 15 >>> / \ >>> 14 13 >>> / \ / \ >>> 12 11 10 9 >>> /\ /\ /\ /\ >>> 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 <[email protected]> >>> >>>> 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 >>>> <[email protected]>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 [email protected]. >>>> 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 [email protected]. >>> 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 [email protected]. > 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 [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
