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

# | User | Rating |
---|---|---|

1 | tourist | 3882 |

2 | maroonrk | 3539 |

3 | Benq | 3513 |

4 | MiracleFaFa | 3466 |

5 | ksun48 | 3462 |

6 | ecnerwala | 3446 |

7 | slime | 3428 |

8 | Um_nik | 3426 |

9 | jiangly | 3401 |

10 | greenheadstrange | 3393 |

# | User | Contrib. |
---|---|---|

1 | awoo | 192 |

2 | -is-this-fft- | 191 |

3 | Monogon | 184 |

4 | YouKn0wWho | 182 |

4 | Um_nik | 182 |

6 | antontrygubO_o | 171 |

7 | maroonrk | 169 |

8 | kostka | 165 |

9 | SecondThread | 164 |

9 | errorgorn | 164 |

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/24/2022 22:09:56 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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 ......

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

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

Thanks to Everyone.

@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. :?