heap @ c++ stl - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - heap @ c++ stl (http://forum.oszone.net/showthread.php?t=46663)

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

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

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

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

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

Цитата:

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

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

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

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

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 в библиотеку. Может он что-то делает очень быстро, но я не знаю что..., а значит не знаю, зачем он нужен.

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

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

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