Can you please explain how keeping two heaps min heap and max heap help in finding median in O(1) time?
Regards, Bujji On Aug 3, 7:29 am, Gene <[email protected]> wrote: > This is a great solution. > > On Jul 28, 3:09 am, janak <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]. > > > For more options, visit this group > > > athttp://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.
