Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»[1]) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за операций при сортировке элементов.[2] Алгоритм работает «на месте» — количество задействованной служебной памяти , то есть фиксированное[1].

Анимированная схема алгоритма

Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.

Пирамидальная сортировка была предложена Дж. Уильямсом[en] в 1963 году.[1]

Алгоритм править

 
Пример сортирующего дерева
 
структура хранения данных сортирующего дерева

Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия:

  1. Каждый лист имеет глубину либо  , либо  ,   — максимальная глубина дерева.
  2. Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.

Удобная структура данных для сортирующего дерева — такой массив  , что   - элемент в корне, а потомки элемента   являются   и  .

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дерева[источник не указан 2696 дней]:

 
 
при  .
Этот шаг требует   операций.

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем   и  , преобразовываем   в сортирующее дерево. Затем переставляем   и  , преобразовываем   в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда   - упорядоченная последовательность.

Этот шаг требует   операций.

Достоинства и недостатки править

Достоинства:

  • Имеет доказанную оценку худшего случая  .
  • Сортирует на месте, то есть требует всего   дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки:

Сортировка слиянием при расходе памяти   быстрее (  с меньшей константой) и не подвержена деградации на неудачных данных.

Из-за сложности алгоритма выигрыш получается только на больших  . На небольших   (до нескольких тысяч) быстрее сортировка Шелла.

Применение править

Пирамидальная сортировка активно применяется в ядре Linux[3].

Примечания править

  1. 1 2 3 4 Курс лекций «Современные технологии параллельного программирования», Лекция № 5: Пирамидальная сортировка. Дата обращения: 20 марта 2009. Архивировано из оригинала 15 марта 2009 года.
  2. ScienceDirect — Journal of Algorithms : The Analysis of Heapsort. Дата обращения: 30 сентября 2017. Архивировано 4 июня 2012 года.
  3. sort.c « lib - kernel/git/torvalds/linux.git - Linux kernel source tree. git.kernel.org. Дата обращения: 7 июля 2023. Архивировано 7 июля 2023 года.

Литература править

  • Левитин А. В. Глава 6. Метод преобразования: Пирамиды и пирамидальная сортировка // Алгоритмы. Введение в разработку и анализМ.: Вильямс, 2006. — С. 275—284. — 576 с. — ISBN 978-5-8459-0987-9
  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 182—188. — ISBN 5-8459-0857-4.

Ссылки править