|
|
|
|
|
|
|
Вернуться
| 1 Mиша Панявин [PML], 15 сентября 2010 г. 12:19:43 | |
|
Спасибо я об этом думал, но испугался "писанины", а оказывается на деле всё проще.
|
|
|
| 2 dAFTc0d3r Делюкин Максим, 14 сентября 2010 г. 17:08:13 | |
|
Ну я это и имел в виду под: "Удалением вершины и перестроением кучи" :)
|
|
|
| 3 dAFTc0d3r Делюкин Максим, 14 сентября 2010 г. 9:45:56 | |
А как мы в куче найдём первые k элементов? Удалением вершины и перестроением кучи?
Можно и кучей в принципе тогда.
А почему set будет долго работать?
Элементарно, за K*log(N). В вершине будем хранить максимум, а извлекая будем его удалять. Если удалять не нужно, то проще потом их добавлять обратно, нежели всю кучу сохранять в массив (чтобы порядок не нарушался). Полагаю, что структура самого сета такова, что он медленнее. Еще смотря как его использовать.
|
|
|
| 4 Беляев Сергей Николаевич, 14 сентября 2010 г. 9:39:33 | |
|
На самом деле куча вполне подойдет, только реализовывать ручками прийдется, т.к. придется хранить позиции элементов. Получается, что все операции с одним элементом требуют O(log n). Множества не советую, будет медленнее.
|
|
|
| 5 dAFTc0d3r Делюкин Максим, 14 сентября 2010 г. 0:08:07 | |
for (int i=0; i <k && sii != si.begin(); ++i) {
--sii;
printf("%d ",*sii);
}
|
|
|
| 6 dAFTc0d3r Делюкин Максим, 13 сентября 2010 г. 23:58:48 | |
ну так всякий set подойдёт наверное
set <int> si;
set <int> :: iterator sii;
...
si.insert(value);
...
sii = lower_bound(si.begin(),si.end(),value); //как-то так
si.erase(sii);
...
sii = si.end;
for (int i=0; i <k && sii != si.begin(); ++i) {
--si;
printf("%d ",*sii);
}
|
|
|
| 7 SKYDOS [Vladimir SU] [skydos.blogspot.com], 13 сентября 2010 г. 21:44:08 | |
|
вернее не хип, тупанул.. дерево, всякие там SortedList(), Sorted*** и прочее.
|
|
|
| 8 SKYDOS [Vladimir SU] [skydos.blogspot.com], 13 сентября 2010 г. 21:43:12 | |
|
как вариант Система непересекающихся множеств для (1) и (2) и heap для (3) с СНМ(система неперсек. множ.)
|
|
|
| 9 Панявин Михаил [HKL], 13 сентября 2010 г. 19:30:39 | |
Нужно уметь делать три операции над множеством:
1) добавлять элемент в множество
2) извлекать элемент из множества
3) получать К самых больших из множества
P.S. просто отсортированный массив не подойдёт - долго добавляет и извлекает.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
