Алгоритм sort_heap()
|
template< class RandomAccessIterator > void sort_heap( RandomAccessIterator first, RandomAccessIterator last );
template< class RandomAccessIterator, class Compare > void sort_heap( RandomAccessIterator first, |
RandomAccessIterator last, Compare comp );
sort_heap()
сортирует последовательность в диапазоне [first,last), предполагая, что это правильно построенный хип; в противном случае поведение программы не определено. (Разумеется, после сортировки хип перестает быть хипом!) В первом варианте при сравнении используется оператор “меньше”, определенный для типа элементов контейнера, а во втором – операция comp.
|
#include <algorithm> #include <vector> #include <assert.h>
template <class Type> void print_elements( Type elem ) { cout << elem << " "; }
int main() { int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 }; vector< int, allocator > vec( ia, ia+12 );
// печатается: 51 35 40 23 29 20 26 22 19 12 17 15 make_heap( &ia[0], &ia[12] ); void (*pfi)( int ) = print_elements; for_each( ia, ia+12, pfi ); cout << "\n\n";
// печатается: 12 17 15 19 23 20 26 51 22 29 35 40 // минимальный хип: в корне наименьший элемент make_heap( vec.begin(), vec.end(), greater<int>() ); for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
// печатается: 12 15 17 19 20 22 23 26 29 35 40 51 sort_heap( ia, ia+12 ); for_each( ia, ia+12, pfi ); cout << "\n\n";
// добавим новый наименьший элемент vec.push_back( 8 );
// печатается: 8 17 12 19 23 15 26 51 22 29 35 40 20 // новый наименьший элемент должен оказаться в корне push_heap( vec.begin(), vec.end(), greater<int>() ); for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
// печатается: 12 17 15 19 23 20 26 51 22 29 35 40 8 // наименьший элемент должен быть заменен на следующий по порядку
pop_heap( vec.begin(), vec.end(), greater<int>() ); for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n"; |