Алгоритмы и структуры данных. Лекция 7. Пирамидальная сортировка (Heap sort) на Python

• Пирамидальная сортировка, также известная как хип-сорт или сортировка кучи, основана на структуре данных куча.  

• На первом шаге алгоритма формируется двоичная куча из входного массива.  

• На каждом шаге значение из корня кучи записывается в последнюю позицию несортированного массива.  

• Размер кучи уменьшается на единицу до тех пор, пока в куче не останется один элемент.  

• Пример: исходный массив, куча, максимальный элемент в корне, заполнение списка или массива.  

• Объявление типа данных и объектов, создание класса хип.  

• Методы добавления и извлечения элемента из кучи.  

• Создание экземпляра класса куча и обход по уменьшению.  

• Извлечение элемента из кучи и помещение его на итую позицию.  

• Пример сортировки списка сотрудников по ID и имени.  

• Временная сложность алгоритма: O n log n.  

• В худшем случае требуется O n дополнительной памяти, в лучшем случае - постоянное значение.