Can anyone tell me where to find ..really nice article on it....
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.04.2024 13:24:25 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
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