Алгоритмы сортировки. Алгоритмы для работы с кучей

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

   
Перечислим алгоритмы для работы с кучей:

  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) сравнений).

   
На следующем шаге мы рассмотрим пример использования алгоритмов для работы с кучей.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий