Алгоритмы для работы с хипом

Алгоритмы для работы с хипом

В стандартной библиотеке используется макс-хип. Макс-хип - это представленное в виде массива двоичное дерево, для которого значение ключа в каждом узле больше либо равно значению ключа в каждом из узлов-потомков. (Подробное обсуждение макс-хипа можно найти в [SEDGEWICK88]. Альтернативой ему является мин-хип, для которого значение ключа в каждом узле меньше либо равно значению ключа в каждом из узлов-потомков.) В реализации из стандартной библиотеки самое большое значение (корень дерева) всегда оказывается в начале массива. Например, приведенная последовательность букв удовлетворяет требованиям, накладываемым на хип:

X T O G S M N A E R A I

В данном примере X - это корневой узел, слева от него находится T, а справа - O. Обратите внимание, что потомки не обязательно должны быть упорядочены (т.е. значение в левом узле не обязано быть меньше, чем в правом). G и S - потомки узла T, а M и N - потомки узла O. Аналогично A и E - потомки G, R и A - потомки S, I - левый потомок M, а N - листовой узел без потомков.

Четыре обобщенных алгоритма для работы с хипом: make_heap(), pop_heap(), push_heap() и sort_heap() - поддерживают его создание и различные манипуляции. В последних трех алгоритмах предполагается, что последовательность, ограниченная парой итераторов, - действительно хип (в противном случае поведение программы не определено). Заметим, что список нельзя использовать как контейнер для хранения хипа, поскольку он не поддерживает произвольный доступ. Встроенный массив для размещения хипа использовать можно, но в этом случае трудно применять алгоритмы pop_heap() и push_heap(), так как они требуют изменения размера контейнера. Мы опишем все четыре алгоритма, а затем проиллюстрируем их работу на примере небольшой программы. Алгоритм make_heap()

template class RandomAccessIterator

void

make_heap( RandomAccessIterator first,

RandomAccessIterator last );

templateclass RandomAccessIterator, class Compare

void

make_heap( RandomAccessIterator first,

RandomAccessIterator last, Compare comp );

make_heap() преобразует в хип последовательность, ограниченную диапазоном [first,last). В первом варианте для сравнения используется оператор "меньше", определенный для типа элементов контейнера, а во втором - операция comp. Алгоритм pop_heap()

template class RandomAccessIterator

void

pop_heap( RandomAccessIterator first,

RandomAccessIterator last );

template class RandomAccessIterator, class Compare

void

pop_heap( RandomAccessIterator first,

RandomAccessIterator last, Compare comp );

pop_heap() в действительности не исключает наибольший элемент, а переупорядочивает хип. Он переставляет элементы в позициях first и last-1, а затем перестраивает в хип последовательность в диапазоне [first,last-1). После этого “вытолкнутый” элемент можно получить посредством функции-члена back() контейнера либо по-настоящему исключить его с помощью pop_back(). В первом варианте при сравнении используется оператор "меньше", определенный для типа элементов контейнера, а во втором - операция comp. Алгоритм push_heap()

template class RandomAccessIterator

void

push_heap( RandomAccessIterator first,

RandomAccessIterator last );

template class RandomAccessIterator, class Compare

void

push_heap( RandomAccessIterator first,

RandomAccessIterator last, Compare comp );

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

template class RandomAccessIterator

void

sort_heap( RandomAccessIterator first,

RandomAccessIterator last );

template class RandomAccessIterator, class Compare

void

sort_heap( RandomAccessIterator first,

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 };

vectorint, 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 " ";

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

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

make_heap( vec.begin(), vec.end(), greaterint() );

for_each( vec.begin(), vec.end(), pfi ); cout " ";

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

sort_heap( ia, ia+12 );

for_each( ia, ia+12, pfi ); cout " ";

// добавим новый наименьший элемент

vec.push_back( 8 );

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

// новый наименьший элемент должен оказаться в корне

push_heap( vec.begin(), vec.end(), greaterint() );

for_each( vec.begin(), vec.end(), pfi ); cout " ";

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

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

pop_heap( vec.begin(), vec.end(), greaterint() );

for_each( vec.begin(), vec.end(), pfi ); cout " ";

}

2014-04-14 18:12:00 Sherzod

Я Началь учится на С++ Отлычно Спосибо

2011-12-10 15:00:54 kaban

какая разница на каком языке писать, на каком языке разговаривать? язык - это средство выражения твоих мыслей. если задачи относительно просты, то даже и спорить нечего - мочим их на языках высокого уровня.. там и думать то ненадо. с++ мало подходит для повседневки. это только если нужно выразить что-то не имеющее границ. с++ крайне изощрен

2011-10-23 00:59:28 Kraner

Я начал учить с++ с 14 лет . Года два на нем прогал и чувствовал постоянную кашу в голове. Там довольно много тонкостей и это отрицать нельзя. После того как годик покодил на паскале все то знал о плюсах структурировалось гораздо лучше. Не обязательно паскаль , можно начинать и с basic , еще лучше наверно начинать с assembler , но это вообще в идеале. Теперь я уже 6 лет программирую на плюсах и ими доволен больше чем каки м либо другим языком . С моей стороны это язык наиболее развязывающий программисту руки и дающий ему полный контроль над тем как делать и что делать .

2011-09-23 16:47:26 Михаил

У меня с++ идёт по программе обучения в универе.и мне надо его учить по любому,и кстати если понимать,то можно начинать и с него=) Kraner ты не прав(а) Николай +

2011-08-31 17:34:09 Kraner

Хотя бы Pascal . Допустим тина указателей в c++ может легко помочь завязнуть надолго любому кто только пытается вникнуть в лес плюсов. Pascal же как то подобрее к начинающим.

2011-08-10 19:47:09 Николай

XD Самый трушный комментарий который я когда либо видел, +1 . Но думаю , что c++ не тот язык с которого надо начинать программировать в таком возрасте . Так тогда назовите с какого надо языка начать с асма так.

2011-07-11 00:09:05 Kraner

XD Самый трушный комментарий который я когда либо видел, +1 . Но думаю , что c++ не тот язык с которого надо начинать программировать в таком возрасте .

2011-05-14 19:09:11 Gor

Я Началь учится на С++ Отлычно Спосибо