coll.beg1n()+3. Граничный элемент coll.endO. Конец интервала

greater<int>()): Критерий сортировки

Вывод

cout « "the four highest elements are: ": copy (coll.beginO. coll .begin()+4.

ostream iterator<int>(cout." ")): cout « endl:

Результат выполнения программы выглядит так:

345672345612345

the four lowest elements are: 2 12 3

the four highest elements are: 5 6 7 6

the four highest elements are: 6 7 6 5

Сортировка в куче

в контексте сортировки кучей (heap) называется бинарное дерево, реализованное в виде последовательной коллекции. Кучи обладают двумя важными свойствами:

О первый элемент всегда является максимальным;

О добавление и удаление элементов производится с логарифмической сложностью.

Куча является идеальной основой для реализации приоритетных очередей (очередей, которые автоматически сортируют свои элементы), поэтому алгоритмы, работающие с кучей, используются контейнером priority queue (см. с. 438). В STL определены четыре алгоритма для работы с кучами:

О алгоритм malce heap() преобразует интервал элементов в кучу;

О алгоритм push heap() добавляет новый элемент в кучу;

О алгоритм pop heap() удаляет элемент из кучи;

О алгоритм sort heap() преобразует кучу в упорядоченную коллекцию (которая после этого перестает быть кучей).

Как обычно, критерий сортировки может задаваться бинарным предикатом. По умолчанию сортировка осуществляется оператором <.

Алгоритмы для работы с кучей

void

make heap (RandomAccessIterator beg. RandomAccessIterator end) void

make heap (RandomAccessIterator beg. RandomAccessIterator end, BinaryPredicate op)

о Обе формы преобразуют элементы интервала [beg,end) в кучу.

О В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки: op(elem1 ,elem2).

О Алгоритмы необходимы лишь для начала работы с ьсучей, содержащей более одного элемента (один элемент автоматически является кучей).

О Сложность: линейная (не более "numberOfElements сравнений).

void

push heap (RandomAccessIterator beg. RandomAccessIterator end) void

push heap (RandomAccessIterator beg. RandomAccessIterator end, BinaryPredicate op)

О Обе формы добавляют последний элемент, находящийся перед end, в существующую кучу [beg,end-\), в результате чего весь интервал \beg,end) становится кучей.

О В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки: op(elem1,elem2).

О Перед вызовом необходимо проследить за тем, чтобы элементы в интервале [beg,end-i) формировали кучу (с общим критерием сортировки), а новый элемент следовал непосредственно за ними.

О Сложность логарифмическая (не более \og(number Of Elements) сравнений).

void

pop heap (RandomAccessIterator beg, RandomAccessIterator end) void

pop heap (RandomAccessIterator beg. RandomAccessIterator end. BinaryPredicate op)

О Обе формы перемещают максималыштй (то есть первый) элемент кучи [begend) в конец и создают новую кучу из оставпшхся элементов в интервале [begfind-\),

О В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки: op(elem1,elem2).

О Перед вызовом необходимо проследить за тем, чтобы элементы в интервале begend-1) формировали кучу (с общим критерием сортировки).

О Сложность логарифмическая (не более 2y\og{numberOfElements) сравнений), void

sort heap (RandomAccessIterator beg. RandomAccessIterator end) void

sort heap (RandomAccessIterator beg. RandomAccessIterator end. BinaryPredicate op)

О Обе формы преобразуют кучу [beg,end) в упорядоченный интервал.

О В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки: op(elem1,elem2).

О После вызова интервал перестает быть ьсучей.

О Перед вызовом необходимо проследить за тем, чтобы элементы в интервале [beg,end-l) формировали кучу (с общим критерием сортировки).

О Сложность логарифмическая (не более number ОfElementsyXognumberOf-Elements) сравнений).

Пример использования алгоритмов для работы с кучей

Следующая программа демонстрирует использование различных алгоритмов работы с кучей:

algo/heapl.cpp #include "algostuff.hpp" using namespace std;

int mainO {

vector<int> coll:

INSERTJLEMENTSCcoll .3.7) IN5ERTJLEMENTS(coll .5.9) lNSERT ELEMENTS(coll.l.4)

PRINT ELEMENTS (coll. "on entry: ");

Преобразование коллекции в кучу make heap (coll.beginO. coll.endO);

PRINTJLEMENTS (coll. "after make heap(); ");

Извпечение следующего элемента из кучи popjeap (coll.beginO, coll.endO); coll. pop Jack О:

PRINTJLEMENTS (COll. "after popJeapO; ");

Занесение нового элемента в кучу coll.push back (17); pushjeap (coll.beginO. coll.endO);

PRINTJLEMENTS (coll, "after push heap(); ");

/* Преобразование кучи в упорядоченную коллекцию * - ВНИМАНИЕ; после вызова интервал перестает быть кучей */

sortjeap (coll.beginO. coll.endO); PRINTJLEMENTS (coll. "after sortJeapO: ");