yeah implementation is wrong. On 3/24/13, tec <technic....@gmail.com> 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 <rahul23111...@gmail.com> > >> 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 >> <rahul23111...@gmail.com>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.
