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