template< class RandomAccessIterator > void

push heap( RandomAccessIterator first, RandomAccessIterator last );

template< class RandomAccessIterator, class Compare > void

push heap( RandomAccessIterator first,

Алгоритм push heap()

RandomAccessIterator last, Compare comp );

push heap() предполагает, что последовательность, ограниченная диапазоном [first,last-1) , - хип и что новый добавляемый к хипу элемент находится в позиции last-1. Все элементы в диапазоне [first,last) реорганизуются в новый хип. Перед вызовом push heap() необходимо вставить новый элемент в конец контейнера, возможно, применив функцию push back() (это показано в примере ниже). В первом варианте при сравнении используется оператор меньше , определенный для типа элементов контейнера; во втором - операция comip.

template< class RandomAccessIterator > void

sort heap( RandomAccessIterator first, RandomAccessIterator last );

template< class RandomAccessIterator, class Compare > void

sort heap( RandomAccessIterator first,

Алгоритм sort heap()

RandomAccessIterator last, Compare comp );

sort heap() сортирует последовательность в диапазоне [first,last) , предполагая, что это правильно построенный хип; в противном случае поведение программы не определено. (Разумеется, после сортировки хип перестает быть хипом!) В первом варианте при сравнении используется оператор меньше , определенный для типа элементов контейнера, а во втором - операция comp.

#include <algorithm> #include <vector> #include <assert.h>

template <class Type>

void print elements( Type elem ) { cout << elem << ; }

int main() {

int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };

vector< int, allocator > vec( ia, ia+12 );

печатается: 51 35 40 23 29 20 26 22 19 12 17 15

make heap( &ia[0], &ia[12] ); void (*pfi)( int ) = print elements; for each( ia, ia+12, pfi ); cout << \n\n ;

печатается: 12 17 15 19 23 20 26 51 22 29 35 40

минимальный хип: в корне наименьший элемент

make heap( vec.begin(), vec.end(), greater<int>() ); for each( vec.begin(), vec.end(), pfi ); cout << \n\n ;

печатается: 12 15 17 19 20 22 23 26 29 35 40 51

sort heap( ia, ia+12 ); for each( ia, ia+12, pfi ); cout << \n\n ;

добавим новый наименьший элемент vec.push back( 8 );

печатается: 8 17 12 19 23 15 26 51 22 29 35 40 20

нов наеньш элемент доен оказаться в корне push heap( vec.begin(), vec.end(), greater<int>() );

for each( vec.begin(), vec.end(), pfi ); cout << \n\n ;

печатается: 12 17 15 19 23 20 26 51 22 29 35 40 8

/ / наень элемент доен быть заменен на следую по порядку

pop heap( vec.begin(), vec.end(), greater<int>() ); for each( vec.begin(), vec.end(), pfi ); cout << \n\n ;

подвижн1е (volatile), 611-14

#include, директива

использование с using-директивой, 68, 427 деструктор(ы)

использование с директивой связывания, 354 для элементов масс??а

освобождение динамической памяти, 693* 94

abort(), функция

умножения оператор вызов из terminate() как подразумеваемое

комплексн1х чисел, 155 поведение, 541

abs(), функция

члены класса функции-члены

K0HCTаHTHIе, 611-14 adjacent find(), обобщенный алгоритм, 1107

поддержка для комплексн1х чисел, 156 accumulate(), обобщенный алгоритм, 1104 adjacent difference(), обобщенн1й алгоритм, 1106

ainooi

к базовому классу, 880-88 algorithm, заголовочн1й файл, 584 any(), функция

в классе bitset, 167 append(), функция

конкатенация строк, 287 argc, переменная

счетчик аргументов в командной строке, 356 argv, массив

для доступа к аргументам в командной строке, 356 assert(), макрос, 51

использование для отладки, 226 at(), функция

контроль выхода за граница: диапазона во время выполнения, 289 atoi(), функция

применение для обработки аргументов в командной строке, 360 auto ptr, шаблон класса, 39500

memory, заголовочный файл, 395

инициализация, 397

подводные камни, 399 aункции

интерфейс

включение объявления исключений в, 546

back(), функция

поддержка очереди, 316 back inserter(), адаптор функции

использование в операции вставки push back(), 577 begin(), функция

итератор

возврат с помощью, 578 использование, 261 binary search(), обобщенный алгоритм, 1108 bind1st(), адаптор функции, 573 bind2nd(), адаптор функции, 573 bitset, заголовочный файл, 168 bitset, класс, 165

size(), функция, 167

test(), функция, 167

to long(), функция, 170

to string(), функция, 170

заголовочный файл bitset, 168

оператор доступа к биту ([]), 167

операции, 168-71 break, 218-19 break, инструкция

использование для выхода из инструкции switch, 203

сравнение с инструкцией return, 346

C, язык

символьные строки

динамическое выделение памяти для, 401 необходимость доступа из класса string,

отсутствие завершающего нуля как программная ошибка, 402 C str(), функция

преобразование объектов класса string в C-строки, 137 C++, язык

std, пространство имен, 426-28 введение в (глава), 12-13 компоненты (часть 2), 319

типы данных (глава), 98-140 предопределенные операторы (таблица), 727 case, ключевое слово

использование в инструкции switch (таблица),

catch-обработчик, 62, 534, 537 критерий выбора, 63 определение, 537

универсальный обработчик, 543-45 cerr, 26

представление стандартного вывода для ошибок с помощью, 1041 char *, указатель

работе! с С-строками символов, 92 char, тип, 76

check range(), пример функции

как закрытая функция-член, 51 cin, 26

использование итератора istreamiterator, 579 представление стандартного ввода с

помощью, 1041 class, ключевое слово

typename как синоним, 479 использование в определении класса, 594 использование в определении шаблона

класса, 801

использование в параметрах-типах шаблона класса, 800 функции, 476 const, квалификатор

вопросы разрешения перегрузки функций

параметры-типы, 432 вопросы разрешения перезагрузки функций использование преобразования

квалификаторов, 449 ранжирование преобразований, связанных с инициализацией ссылочных параметров, 473 константная функция-член, 611-14 константные объекты, динамическое

выделение и освобождение памяти, 402-3 константные параметры

параметры-ссылки с квалификатором

const, 330, 340

передача массива из константных элементов, 336 константный итератор, 262 контейнеры, необходимость константного

итератора, 575 преобразование объектов в константы, 101 сравнение с volatile, 127 ссылка, инициализация объектом другого

типа, 105

указатели на константные объекты, 101