490_____________________Часть III. Современное программирование на C++

push_heap. Алгоритмы для данных типа heap (куча) — push_heap, pop_heap, make_heap и sort_heap работают со специальными конструкциями упорядо-ченных элементов, называемых бинарными деревьями (binary tree). Элементы в них легко добавляются и удаляются. Куча определяется на последовательности элементов с произвольным доступом [first, last), в которой

*first — наибольший элемент в куче. Вследствие ограничений для итераторов с произвольным доступом, эти алгоритмы работают только с векторами и двусторонними очередями. Благодаря своей структуре они наиболее эффективны для работы с приоритетными очередями.

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-l), новый элемент, на который указывает значение last.

popJiedp. Удаляет наибольшее значение *first в куче определяемой диапазоном [first, last). Это выполняется с помощью перестановки *first и

*(last-l). Таким образом в выходной последовательности новая куча будет определяться диапазоном [first, last-l), а итератор last-i будет указывать на нужный элемент.

template <class RandomAccessIterator> void pop_heap (RandomAccessIterator first, RandomAccessIterator last) ;

template <class RandomAccessIterator, class Compare> void pop_heap (RandomAccessIterator first,

RandomAccessIterator last. Compare comp) ;

make_heap. Строит кучу по неупорядоченной входной последовательности.

:emplate <class RandomAccessIterator> inline void make heap (RandomAccessIterator first, RandomAccessIterator last) ;

:emplate <class RandomAccessIterator, class Compare> ^oid make_heap (RandomAccessIterator first,

RandomAccessIterator last, Compare comp) ;

.ort_heap. Строит последовательность упорядоченных элементов из вход-юй кучи, определяемой диапазоном [first, last).

:emplate <class RandomAccessIterator> 'old sort_heap (RandomAccessIterator first, RandomAccessIterator last);