[algogeeks] Re: Median in stream of running integers
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
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.
[algogeeks] Need to know about Accolite
Hi All, I got offer from Accolite, bangalore. Can anyone tell how is the company? -Revati Raman -- 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.