How about keeping heap? Have two heaps 1. max heap and 2. min heap keep them equal size all the time and shift top element from one to other when required...
On Wed, Jul 28, 2010 at 7:46 AM, Gene <gene.ress...@gmail.com> wrote: > I think you have confused the statement of this problem. The "(in > sorted order)" comment makes no sense because a median is exactly one > number. One number is always sorted. > > After every stream element is read, you want to be able to get the > median of all elements read so far. > > You're correct that the way to do this is maintain the elements in > some kind of sorted data structure where you have O(1) access to the > middle element. An array or list will work fine, but each stream > element will require O(n) to insert in the sorted order (just as you'd > do for insertion sort). It's easy to use a balanced tree instead. > This reduces the processing time for each element to O(log n). You > must maintain the invariant that the root of the tree is the median, > so access time is still O(1). When a new element is read, it goes in > either the left or right subtree of the root. This may cause the > median to shift by 0 or 1 position in either direction. In this case, > you'll always be able to pull the successor or predecessor of the > root--whichever is the new median--up to the root by using e.g. AVL > rotations. You'd have to prove that this does not make the tree too > unbalanced so that the O(log n) insertion is hurt, but I don't think > this would be hard. > > On Jul 24, 10:32 am, jalaj jaiswal <jalaj.jaiswa...@gmail.com> wrote: >> You are given a stream of numbers which can be positive or negative. You are >> required to provide an operation FIND MEDIAN..which when invoked should be >> able return the median of the numbers in stream (in sorted order) in O(1) >> time. >> >> Eg: 0 1 2 3 4 >> Right FIND MEDIAN returns 2 as median >> >> Now input is -2 -4 >> So Stream = 0 1 2 3 -2 -2 -4 >> Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1 >> >> -- >> With Regards, >> Jalaj Jaiswal >> +919026283397 >> B.TECH IT >> IIIT ALLAHABAD > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
