I posted a more complete solution but it seems to have disappeared. Set up 2 heaps Lo and Hi where Lo has the max at its root and Hi has the min. I.e., Lo is a max heap and Hi is a min heap.
Also maintain a variable M. Establish the invariants: 1. N(Lo) = N(Hi) where N(H) is the number of elements in H. 2. max(Lo) <= min(Hi) 3. If M is not empty, then max(Lo) <= M <= min(Hi) >From these you can conclude the following: 1. If M is empty and we have already read some elements, then: Median = (max(Lo) + min(Hi)) / 2. 2. Else M is not empty, then: Median = M Certainly all these inveriants are true when Lo, Hi, and M are all empty. Now it turns out that every time you read a new element, you can add it to one of Lo, Hi, or M and then adjust everything so that the invariants are re-established. This can be accomplished with only a constant number of O(log n) operations. The cases to figure out are: M is not empty and A > M. M is not empty and A = M. M is not empty and A < M. M is empty and the new element A > min(Hi) M is empty and the new element A < max(Lo) M is empty and max(Lo) <= A <= min(Hi). This covers all possible cases, so if you can work out what to do for each one, you are done. I'm not going to spoil the rest of the fun for you. On Aug 3, 1:37 am, bujji <jajalabu...@gmail.com> wrote: > Can you please explain how keeping two heaps min heap and max heap > help in findingmedianin O(1) time? > > Regards, > Bujji > > On Aug 3, 7:29 am, Gene <gene.ress...@gmail.com> wrote: > > > > > This is a great solution. > > > On Jul 28, 3:09 am, janak <chandar...@gmail.com> wrote: > > > > 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 amedianis exactly one > > > > number. One number is always sorted. > > > > > After every stream element is read, you want to be able to get the > > > >medianof 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 themedian, > > > > 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 > > > >medianto 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 newmedian--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 FINDMEDIAN..which when invoked should > > > >> be > > > >> able return themedianof the numbers in stream (in sorted order) in O(1) > > > >> time. > > > > >> Eg: 0 1 2 3 4 > > > >> Right FINDMEDIANreturns 2 asmedian > > > > >> 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 FINDMEDIANreturns 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 > > > > athttp://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - > > > - Show quoted text -- 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 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.
