Задачи по Python с решениями

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

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

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

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

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

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

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