Please check the DS Symmetric Min-Max Heap, the root node is empty in this DS, we can use of this and use the root always median.
I think this will give the median with O(1) and insertion and deletion costs O(logN). Thanks & regards, Sathaiah Dontula On Tue, Aug 3, 2010 at 7:59 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 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<algogeeks%2bunsubscr...@googlegroups.com> > . > > > For more options, visit this group athttp:// > 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<algogeeks%2bunsubscr...@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.
