C++ для начинающих

Алгоритмы для работы с хипом

В стандартной библиотеке используется макс-хип. Макс-хип - это представленное в виде массива двоичное дерево, для которого значение ключа в каждом узле больше либо равно значению ключа в каждом из узлов-потомков. (Подробное обсуждение макс-хипа можно найти в [SEDGEWICK88]. Альтернативой ему является мин-хип, для которого значение ключа в каждом узле меньше либо равно значению ключа в каждом из узлов-потомков.) В реализации из стандартной библиотеки самое большое значение (корень дерева) всегда оказывается в начале массива. Например, приведенная последовательность букв удовлетворяет требованиям, накладываемым на хип:

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,