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.
