acc1's blog

Median Heap...yeah mmm...
By acc1, 14 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

Comments Comments (4)
| Write comment?
14 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?
→ Reply
14 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.

→ Reply
  • 14 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 ......

    → Reply
    • 14 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
      → Reply