heap @ c++ stl

[pva]

Что такое heap в C++ STL и как его можно эффективно использовать?
Когда он лучше, чем max_element() или sort()?

[hasherfrog]

>> Что такое heap в C++ STL
Шаблон такой, емнип.

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

[hasherfrog]

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclang98/HTML/sample_heap_(STL_Sample).asp

[pva]

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

[pva]

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

[hasherfrog]

pva
>> Я стараюсь при прочих равных условиях повышать эффективность
Дык это, хорошо. Считайте, что у меня такой неуклюжий юмор.

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

[pva]

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

// heap

vector<int> v(10);
// fill ...
make_heap(v.begin(), v.end());
sort_heap(v.begin(), v.end())

// sort

vector<int> 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-пакетов).

[pva]

http://anatolix.naumen.ru/Books/cplusplus
Там много прикольных статей; советую:
Exceptional C++, More Exceptional C++ (Решение сложных задач на C++)

[hasherfrog]

Спасибо.