о Первая форма сортирует элементы оператором <.

О Вторая форма сортирует элементы по критерию ор{е1ет1 ,elem2).

О Предиьсат ор не должен изменять свое состояние во время вызова. За подробностями обращайтесь на с. 303.

О Алгоритм partitionO (см. с. 387) тоже разбивает элементы интервала на две части но заданному критерию сортировки. Отличия между partitionO и ntii elernent() описаны на с. 330,

О Сложность в среднем линейная.

Пример использования алгоритма nth element:

algo/ntlil.cpp Iinclude algostuff.hpp using namespace std;

int mainO (

deque<int> coll;

INSERT aEMENTS(coll.3.7) INSERT ELEMENTS(coll.2.6) INSERT ELEMENTS(coll.l.5) PRINTJLEMENTSCcoll);

Выделение четырех наименьших элементов nth element (coll.beginO. Начало интервала

coll .beginO+3. Граничный элемент

coll.endO); Конец интервала

Вывод

cout the four lowest elements are: ; copy Ccoll.beglnO. coll .beg1nO+4.

ostreamjterator<int>(cout. )): cout endl:

Выделение четырех наибольших элементов nth element (coll.beginO. Начало интервала

coll.end()-4. Граничный злемент

coll.endO); Конец интервала

Вывод

cout the four highest elements are; ; copy (coll .end()-4. coll.endO.

ostreamJterator<int>(cout. )): cout endl:

Выделение четырех наибольших элементов (второй вариант) nth element (coll.beginO. Начало интервала

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

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

Вывод

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

ostream 1terator<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).