Adding to Dave's Explanation. Algo goes something like this,
while Adding a random number - Have two heaps ie a MaxHeap(For storing numbers less than the median) and a MinHeap(for numbers > the median). - We will make sure that the median is the top element in the maxHeap meaning that the MaxHeap will always be one greater than or equal to the size of the minHeap - If the size of the two heaps are equal and if the random number is greater than the value in the min heap,remove the top element from the min heap and push it to the max heap and push the random number into the minHeap. else push the random number into the maxHeap - If the size of the two heaps are not equal(assuming that the maxHeap has one more than the minHeap) and if the random number is greater than or equal to the value in the min heap, push it to the maxHeap else, remove the top element from the maxHeap and push it to the minHeap and push the random number into the minHeap. getMedian(): - if the size of the two heaps are equal, select the average of the top elements of the two heaps. - if the size of the two heaps are equal, select the top element from the heap with more elements. Thanks, Immanuel On Fri, May 20, 2011 at 10:55 PM, Anand <[email protected]> wrote: > @ Dave. Nice explanation > > > On Fri, May 20, 2011 at 6:06 AM, saurabh agrawal <[email protected]>wrote: > >> Thanks Dave. >> >> On Wed, May 18, 2011 at 8:01 PM, Dave <[email protected]> wrote: >> >>> @Saurabh: You look at the top elements in the two heaps. If the new >>> number is between the values of the top of the heaps, you add it to >>> the shorter of the two heaps, or to either heap if they are of equal >>> length. If the new number is larger than the min of the min-heap, you >>> add it to the min-heap. If it is smaller than the max of the max-heap, >>> you add it to the max heap. If the resulting two heaps differ in >>> length by more than one element, you move the top element from the >>> longer heap into the shorter heap. Since the heaps start off empty and >>> you add only one number at a time, the result of a step of the >>> algorithm is that the two heaps will differ in size by at most one >>> element. Thus, the smaller half of the numbers will be in the max-heap >>> and the larger half will be in the min-heap. >>> >>> Dave >>> >>> On May 18, 8:29 am, saurabh agrawal <[email protected]> wrote: >>> > Dave, >>> > u said:" a max-heap of the smallest >>> > half of the elements" >>> > but if the number are randomply generated, then how will you get to >>> know >>> > whether a number belongs to smallest half OR lager half.. >>> > i didnt got it... >>> > >>> > >>> > >>> > On Sat, May 14, 2011 at 9:10 PM, Dave <[email protected]> wrote: >>> > > @Ashish: The idea is to keep two heaps, a max-heap of the smallest >>> > > half of the elements and a min-heap of the largest elements. You >>> > > insert incoming elements into the appropriate heap. If the result is >>> > > that the number of elements in the two heaps differs by more than 1, >>> > > then you move the top element from the longer heap into the other >>> one, >>> > > thereby equalzing the number of elements. Thus, inserting an element >>> > > is an O(log n) operation. To get the median, it is the top element of >>> > > the longer heap, or, if the heaps are of equal length, it is the >>> > > average of the two top elements. This is O(1). >>> > >>> > > Dave >>> > >>> > > On May 14, 8:34 am, Ashish Goel <[email protected]> wrote: >>> > > > not clear, can u elaborate.. >>> > >>> > > > Best Regards >>> > > > Ashish Goel >>> > > > "Think positive and find fuel in failure" >>> > > > +919985813081 >>> > > > +919966006652 >>> > >>> > > > On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal < >>> [email protected] >>> > > >wrote: >>> > >>> > > > > This problem can be solved using 2 heaps and the median can >>> always be >>> > > > > accessed in O(1) time ,the first node. >>> > >>> > > > > -- >>> > > > > You received this message because you are subscribed to the >>> Google >>> > > Groups >>> > > > > "Algorithm Geeks" group. >>> > > > > To post to this group, send email to [email protected]. >>> > > > > To unsubscribe from this group, send email to >>> > > > > [email protected]. >>> > > > > For more options, visit this group at >>> > > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text >>> - >>> > >>> > > > - Show quoted text - >>> > >>> > > -- >>> > > You received this message because you are subscribed to the Google >>> Groups >>> > > "Algorithm Geeks" group. >>> > > To post to this group, send email to [email protected]. >>> > > To unsubscribe from this group, send email to >>> > > [email protected]. >>> > > For more options, visit this group at >>> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - >>> > >>> > - Show quoted text - >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
