Алгоритм 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";
}
