Глава 14. Алгоритмы

367

makejieap

Алгоритм makejieap выполняет преобразование последовательности с произвольным доступом в пирамиду:

tempiate<class Ran>

void make_heap(Ran first, Ran last); tempiate<class Ran, class Compare>

void make_heap(Ran first, Ran last, Compare comp);

368

Часть III. Стандартная библиотека

popjieap

Алгоритм pop_heap удаляет первый элемент последовательности, а затем восстанавливает условие пирамидальности:

tempiate<class Ran>

void pop__heap(Ran first, Ran last); tempiate<class Ran, class Compare>

void pop_heap(Ran first, Ran last, Compare comp);

Получение значения извлекаемого элемента из пирамиды требуется выполнить обычным образом. Например, для приведенного выше массива а можно записать:

х = *а; pop_heap(a. a + m);

pushjieap

Алгоритм pushjieap выполняет преобразование последовательности в пирамиду после добавления в нее последнего элемента:

tempiate<class Ran>

void push_heap(Ran first, Ran last); tempiate<class Ran, class Compare>

void push_heap(Ran first, Ran last, Compare comp);

Обратите внимание, что до вызова pushjieap требуется добавить элемент в последовательность способом, соответствующим типу контейнера, например:

v.push_back(x); push_heap(v.begin(), v.endO);

sort_heap

Алгоритм sortjieap преобразует пирамиду в отсортированную по возрастанию последовательность:

tempiate<class Ran>

void sort_heap(Ran first, Ran last); tempiate<class Ran, class Compare>

void sort_heap(Ran first, Ran last. Compare comp);

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

Глава 15

Средства для численных расчетов

Обобщенные численные алгоритмы

Для использования численных алгоритмов требуется подключить заголовочный файл <numeric>.

Таблица 15. Обобщенные численные алгоритмы

Алгоритм	Выполняемая функция
accumulate	Накопление
inner_product	Скалярное произведение
partial_sum	Расчет суммы с накоплением
adjacent_di fference	Вычисление разности между смежными элементами

accumulate

Первая форма алгоритма accumulate используется для накопления суммы элементов последовательности, заданной итераторами first и last. Начальное значение суммы (обычно это 0) задается третьим параметром. Тип этого параметра определяет тип результата (функция возвращает вычисленную сумму):

template <class In, class T>

T accumulatedn first, In last, T init);

Вторая форма алгоритма accumulate позволяет выполнять над третьим параметром и очередным элементом последовательности заданную операцию:

template t<class In, class T, class Bin0p>

T accumulatedn first, In last, T init. BinOp binary_op);

В приведенном далее примере вычисляется сумма, произведение и сумма квадратов элементов массива:

370