heap @ c++ stl

[pva]

Что такое heap в C++ STL и как его можно эффективно использовать?

Когда он лучше, чем max_element() или sort()?

[hasherfrog]

>> Что такое heap в C++ STL

Шаблон такой, емнип.



>> как его можно эффективно использовать?

? %)

Если любите с шаблонами работать, почему бы его и не использовать (хоть эффективно, хоть неэффективно)?

[hasherfrog]

Спасибо.

[hasherfrog]

http://msdn.microsoft.com/library/defau ... ample).asp

[pva]

я имею ввиду make_heap, sort_heap. Их примеры я видел, но так и не понял, почему сортировка или поиск максимального элемента хуже.

По поводу эффективного использования, например: для быстрой вставки/удаления в середине контейнера эффективней использовать список, чем вектор. В этом смысле.

[pva]

Цитата:



хоть эффективно, хоть неэффективно



Даже обидно становится. Я стараюсь при прочих равных условиях повышать эффективность

[hasherfrog]

pva

>> Я стараюсь при прочих равных условиях повышать эффективность

Дык это, хорошо. Считайте, что у меня такой неуклюжий юмор.



>> но так и не понял, почему сортировка или поиск максимального элемента хуже.

Почему хуже? Кто сказал, что хуже? Чем хуже? Вы же не объясняете... Остаётся догадываться... Любит человек шаблоны - пишет всё через heap. Ему говорят - так не эффективно, хочешь, пойдём с секундомером замеряем скорость работы- через heap и через qsort. А он говорит - зато у меня текст проги короче. И что? Кто прав?

[pva]

1. Текст проги получается длиннее (если речь о сортировке или макс.элементе)



Код:

Код: Выделить всё

// heap
vector v(10);
// fill ...
make_heap(v.begin(), v.end());
sort_heap(v.begin(), v.end())
// sort
vector v(10);
// fill ...
sort(v.begin(), v.end());

2. В хелпе написано количество операций в среднем необходимых для выполнения действия (3*n для make_heap, n*log(n)/log(2) для sort_heap, n*log(n)/log(2) для sort). Если делать heap, а потом его сортировать, то количество операций немного превосходит sort. Если делать heap и искать максимальный элемент, то количество операций превосходит max_element втрое.



3. Не думаю, что коммитет по стандартизации C++ "просто так" включил heap в библиотеку. Может он что-то делает очень быстро, но я не знаю что..., а значит не знаю, зачем он нужен.

[pva]

Нашёл описание на руском языке в ссылках на документацию. Это нужно для имитации priority queue на векторе. Понятно, что сортировка на heap хуже, чем специализированный алгоритм. Поэтому в примерах только pop_back демонстрируется.

[hasherfrog]

pva

Можно ссылку глянуть? А то я тут как раз написал очередь с приоритетами... А скорость у меня не просто критична, а апупеть как критична (нужно отрабатывать кучу udp-пакетов).