На этом шаге мы приведем общие сведения по сортировке в куче.
В контексте сортировки кучей (heap) называется бинарное дерево, реализованное в виде последовательной коллекции. Кучи обладают двумя важными свойствами:
- первый элемент всегда является максимальным;
- добавление и удаление элементов производится с логарифмической сложностью.
Куча является идеальной основой для реализации приоритетных очередей (очередей, которые автоматически сортируют свои элементы), поэтому алгоритмы, работающие с кучей, используются контейнером priority_queue. В STL определены четыре алгоритма для работы с кучами:
- алгоритм make_heap() преобразует интервал элементов в кучу;
- алгоритм push_heap() добавляет новый элемент в кучу;
- алгоритм pop_heap() удаляет элемент из кучи;
- алгоритм sort_heap() преобразует кучу в упорядоченную коллекцию (которая после этого перестает быть кучей).
Как обычно, критерий сортировки может задаваться бинарным предикатом. По умолчанию сортировка осуществляется оператором <.
На следующем шаге мы рассмотрим алгоритмы, используемые для работы с кучей.
