acc1's blog

By acc1, 11 years ago, In English

Can anyone tell me where to find ..really nice article on it....


 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

11 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Hey)what do u need exactly?are u looking for solution for problem like this one?
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

AFAIK it's a very simple data structure: it can PUSH number in O(log N), and POP_MEDIAN in O(log N). To create it, we can just create two balanced min-heaps (i.e. standard heaps, that can PUSH element in O(log N) and POP_MINIMUM in O(log N)), such that the lowest half of elements is saved in the first heap, and the second half - in the second heap. This allows us to find median quickly: the median is the minimal element of the second heap.

  • 11 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Now, I am wondering can I use STL in C++ for the task rather writing my own Heap...!

    Now I know there is priority_queue available. But it implements either min heap or max heap.

    How to bring them together and make something like Median Heap?

    Changing the comparison function may be the option......I dont know..U tell me ......

    • 11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      >> Now I know there is priority_queue available. But it implements either min heap or max heap.

      Right. If you analyse e-maxx 's comment then you would realise that median heap can be implemented by maintaining two heaps and doing some operations to balance the number of elements in these two heaps.


      You may test your implementation in this problem:
      www.spoj.pl/problems/WEIRDFN
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
So, are you suggesting that ...existing priority_queue will help in making such data structure ...by balancing the number of elements in two priority_queues..!  Hmm...Let me think  how..
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah...It was quite easy after that, balancing the number of elements was easy..

Thanks to Everyone.

11 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

@Rizwan,

I tried to implement it for your link : www.spoj.pl/problems/WEIRDFN

And here is my solution .

But it is giving WA, my guess is that , it might be due to overflow of long long,

I tried to see, but cant locate where is it overflowing. :?