Алгоритмы сортировки. Сортировка в куче (общие сведения)

   
На этом шаге мы приведем общие сведения по сортировке в куче.

   
В контексте сортировки кучей (heap) называется бинарное дерево, реализованное в виде
последовательной коллекции. Кучи обладают двумя важными свойствами:

  • первый элемент всегда является максимальным;
  • добавление и удаление элементов производится с логарифмической сложностью.

   
Куча является идеальной основой для реализации приоритетных очередей (очередей, которые автоматически
сортируют свои элементы), поэтому алгоритмы, работающие с кучей, используются контейнером priority_queue.
В STL определены четыре алгоритма для работы с кучами:

  • алгоритм make_heap() преобразует интервал элементов в кучу;
  • алгоритм push_heap() добавляет новый элемент в кучу;
  • алгоритм pop_heap() удаляет элемент из кучи;
  • алгоритм sort_heap() преобразует кучу в упорядоченную коллекцию (которая после этого перестает быть кучей).

   
Как обычно, критерий сортировки может задаваться бинарным предикатом. По умолчанию сортировка осуществляется
оператором <.

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



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

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