X T O G S M N A E R A I
В данном примере X - это корневой узел, слева от него находится T, а справа - O. Обратите внимание, что потомки не обязательно должны быть упорядочены (т.е. значение в левом узле не обязано быть меньше, чем в правом). G и S - потомки узла T, а M и N - потомки узла O. Аналогично A и E - потомки G, R и A - потомки S, I - левый потомок M, а N - листовой узел без потомков.
Четыре обобщенных алгоритма для работы с хипом: make_heap(), pop_heap(), push_heap() и sort_heap() - поддерживают его создание и различные манипуляции. В последних трех алгоритмах предполагается, что последовательность, ограниченная парой итераторов, - действительно хип (в противном случае поведение программы не определено). Заметим, что список нельзя использовать как контейнер для хранения хипа, поскольку он не поддерживает произвольный доступ. Встроенный массив для размещения хипа использовать можно, но в этом случае трудно применять алгоритмы pop_heap() и push_heap(), так как они требуют изменения размера контейнера. Мы опишем все четыре алгоритма, а затем проиллюстрируем их работу на примере небольшой программы. Алгоритм make_heap()
template class RandomAccessIterator
void
make_heap( RandomAccessIterator first,
RandomAccessIterator last );
templateclass RandomAccessIterator, class Compare
void
make_heap( RandomAccessIterator first,
RandomAccessIterator last, Compare comp );
make_heap() преобразует в хип последовательность, ограниченную диапазоном [first,last). В первом варианте для сравнения используется оператор "меньше", определенный для типа элементов контейнера, а во втором - операция comp. Алгоритм pop_heap()
template class RandomAccessIterator
void
pop_heap( RandomAccessIterator first,
RandomAccessIterator last );
template class RandomAccessIterator, class Compare
void
pop_heap( RandomAccessIterator first,
RandomAccessIterator last, Compare comp );
pop_heap() в действительности не исключает наибольший элемент, а переупорядочивает хип. Он переставляет элементы в позициях first и last-1, а затем перестраивает в хип последовательность в диапазоне [first,last-1). После этого “вытолкнутый” элемент можно получить посредством функции-члена back() контейнера либо по-настоящему исключить его с помощью pop_back(). В первом варианте при сравнении используется оператор "меньше", определенный для типа элементов контейнера, а во втором - операция comp. Алгоритм push_heap()
template class RandomAccessIterator
void
push_heap( RandomAccessIterator first,
RandomAccessIterator last );
template class RandomAccessIterator, class Compare
void
push_heap( RandomAccessIterator first,
RandomAccessIterator last, Compare comp );
push_heap() предполагает, что последовательность, ограниченная диапазоном [first,last-1), - хип и что новый добавляемый к хипу элемент находится в позиции last-1. Все элементы в диапазоне [first,last) реорганизуются в новый хип. Перед вызовом push_heap() необходимо вставить новый элемент в конец контейнера, возможно, применив функцию push_back() (это показано в примере ниже). В первом варианте при сравнении используется оператор "меньше", определенный для типа элементов контейнера; во втором - операция comp. Алгоритм 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 };
vectorint, 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";