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

on entry: 34567567891234

after make heap(): 98677553641234

after pop heap(): 8767455364123

after push heap(): 17 7874563641235

after sort heap(): 1233445566778 17

После вызова make heap() элементы сортируются в виде кучи:

98677553641234

Если преобразовать эту последовательность в бинарное дерево, вы увидите, что значение каждого узла меньше либо равно значению его родительского узла (рис. 9.1). Алгоритмы push heap() и pop heap() изменяют элементы так, что инвариант структуры бинарного дерева (любой узел не больше своего родительского узла) остается неизменным.

Рис. 9.1. Элементы кучи в виде бинарного дерева

Алгоритмы упорядоченных интервалов

Алгоритмы упорядоченных интервалов требуют, чтобы элементы исходных интервалов были упорядочены по своим критериям сортировки. Обычно эти алгоритмы работают гораздо эффективнее своих аналогов для неупорядоченных интервалов (как правило, они обладают логарифмической, а не линейной слож-гюстью). Алгоритмы упорядоченных интервалов могут использоваться с итераторами, которые не являются итераторами произвольного доступа, но в этом случае сложность оказывается линейной, поскольку им приходится последовательно перебирать элемент за элементом. Впрочем, количество сравнений все равно может остаться логарифмическим.

Согласно стандарту, вызов этих алгоритмов для незшорядоченных интервалов приводит к непредсказуемым последствиям. Хотя в большинстве реализаций алгоритмы успешно работают с неупорядоченными последовательностями, использовать их в программе нельзя - это нарушит ее переносимость.

В ассоциативных контейнерах определены специальные функции, аналогичные по назначению представленным далее алгоритмам. При поиске по заданному значению или ключу следует использовать эти функции вместо алгоритмов.

Поиск элементов

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

Проверка npnqfrcTBMfl элемента

bool

binary search (Forwardlterator beg. Forwardlterator end. const T& value) bool

binary search (Forwardlterator beg. Forwardlterator end. const T& value. BinaryPredicate op)

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

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

О Чтобы определить позинию искомого элемента, воспользуйтесь функниями lower bound(), upper bound() и equal range() (см. с. 402).

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

О Сложность логарифмическая для итераторов произвольного доступа, линейная в остальных случаях (не более \og(numberOfElements)+2 сравнений, но для итераторов, не являющихся итераторами произвольного доступа, выполняется линейное количество операпий перебора, вследствие чего сложность оказывается линейной).

Пример использования алгоритма blnary search():

algo/bsearchl.cpp #1nclude "algostuff-hpp" using namespace std:

Int maInO

list<1nt> coll:

INSERT ELEMENTS(coll,1,9): PRINT ELEMENTS(con):

Проверка существования элемента со значением 5 1f (b1nary search(con,beginO. coll.endO. 5)) ( cout « "5 1S present" « endl:

else {

cout « "5 is not present" « endl;

Проверка существования элемента со значением 42 If (binary search(coll .beginO, coll.endO, 42)) { cout « "42 is present" « endl;

else {

cout « "42 is not present" « endl;

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

12 3 4 5 6 7 8 9

5 is present

42 is not present

Проверка присутствия нескольких элементов

bool

includes (Inputlteratorl beg. Inputlteratorl end.

InputIterator2 searchBeg. InputIterator2 searchEnd)

bool

includes (Inputlteratorl beg. Inputlteratorl end.

InputIterator2 searchBeg. InputIterator2 searchEnd. BinaryPredicate op)

О Обе формы проверяют, содержит ли зшорядоченный интервал [beg,end) все элементы зшорядоченного интервала [searchBeg,searchEnd), и возвращают результат в виде логической величины. Иначе говоря, для каждого элемента интервала [searchBeg,searchEnd) должен существовать равный элемент в интервале [beg, end). Если некоторые элементы интервала [searckBeg,searckEnd) равны, то в интервале [beg,end) должно присутствовать такое же количество дубликатов. Таким образом, интервал [searchBeg,searchEnd) должен быть подмножеством интервала [beg,end).

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

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

о Сложность линейная (не более 2x(numberOfElements+searchElements)-\ сравнений).

Пример использования алгоритма lncludes():

algo/includes.cpp finclude "algostuff.hpp" using namespace std;