На этом шаге мы дадим краткую характеристику алгоритмов, предназначенных для работы с кучей.
Перечислим алгоритмы для работы с кучей:
void make_heap (RandomAccessIterator beg, RandomAccessIterator end) void make_heap (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
Обе формы преобразуют элементы интервала [beg,end) в кучу.
В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки: op(elem1,elem2).
Алгоритмы необходимы лишь для начала работы с кучей, содержащей более одного элемента (один элемент автоматически является кучей).
Сложность: линейная (не более 3*mumberOfElements сравнений).
void push_heap (RandomAccessIterator beg, RandomAccessIterator end) void push_heap (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
Обе формы добавляют последний элемент, находящийся перед end, в существующую кучу [beg,end-1), в результате чего весь интервал [beg,end) становится кучей.
В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки: op(elem1,elem2).
Перед вызовом необходимо проследить за тем, чтобы элементы в интервале [beg,end-1) формировали кучу (с общим критерием сортировки), а новый элемент следовал непосредственно за ними.
Сложность логарифмическая (не более log(numberOfElements) сравнений).
void pop_heap (RandomAccessIterator beg, RandomAccessIterator end) void pop_heap (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
Обе формы перемещают максимальный (то есть первый) элемент кучи [beg,end) в конец и создают новую кучу из оставшихся элементов в интервале [beg,end-1).
В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки: op(elem1,elem2).
Перед вызовом необходимо проследить за тем, чтобы элементы в интервале [beg,end-1) формировали кучу (с общим критерием сортировки).
Сложность логарифмическая (не более 2*log(numberOfElements) сравнений).
void sort_heap (RandomAccessIterator beg, RandomAccessIterator end) void sort_heap (RandomAccessIterator beg, RandomAccessIterator end, BinaryPredicate op)
Обе формы преобразуют кучу [beg,end) в упорядоченный интервал.
В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки: op(elem1,elem2).
После вызова интервал перестает быть кучей.
Перед вызовом необходимо проследить за тем, чтобы элементы в интервале [beg,end-1) формировали кучу (с общим критерием сортировки).
Сложность логарифмическая (не более numberOfElements*log(numberOfElements) сравнений).
На следующем шаге мы рассмотрим пример использования алгоритмов для работы с кучей.
