Smoothsort — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Основная идея)
м (rollbackEdits.php mass rollback)
 
(не показаны 63 промежуточные версии 5 участников)
Строка 1: Строка 1:
'''Плавная сортировка''' (англ. Smooth sort) -- алгоритм сортировки, разновидность [[Сортировка кучей|сортировки кучей]], разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную <tex dpi = 120> O(N log N) </tex>. Преимущество плавной сортировки в том, что её сложность приближается к <tex dpi = 120> O(N) </tex>, если входные данные частично отсортированы, в то время как у сортировки кучей сложность всегда одна, независимо от состояния входных данных.
+
'''Плавная сортировка''' (англ. Smooth sort) {{---}} алгоритм сортировки, модификация [[Сортировка кучей|сортировки кучей]], разработанный Э. Дейкстрой. Как и пирамидальная сортировка, в худшем случае работает за время <tex> \Theta(N\log{N}) </tex>. Преимущество плавной сортировки в том, что её время работы приближается к <tex dpi = 120> O(N) </tex>, если входные данные частично отсортированы, в то время как у сортировки кучей время работы не зависит от состояния входных данных.
  
 
==Основная идея==
 
==Основная идея==
Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо:
+
Разовьём идею пирамидальной сортировки. Для этого используем не [[Двоичная куча|двоичную кучу]], а специальную, полученную с помощью чисел Леонардо<ref>[https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9B%D0%B5%D0%BE%D0%BD%D0%B0%D1%80%D0%B4%D0%BE Википедия {{---}}  Числа Леонардо]</ref>, которые задаются следующим образом:
  
<tex dpi = 120> L(0) = 1, L(1) = 1, L(i) = L(i - 1) + L(i - 2) + 1 </tex>
+
<tex>  
 +
  L(n) =
 +
  \begin{cases}
 +
    1               &  \mathrm{if}\ n = 0, \\
 +
    1               &  \mathrm{if}\ n = 1, \\
 +
    L(n-1)+L(n-2)+1 &  \mathrm{if}\ n > 1. \\
 +
  \end{cases}
 +
</tex>
  
 
Вот первые несколько членов этой последовательности:
 
Вот первые несколько членов этой последовательности:
Строка 10: Строка 17:
  
 
{{Утверждение
 
{{Утверждение
|statement= Любое натуральное число представить суммой из <tex dpi = 120> O(log N) </tex> различных чисел Леонардо.
+
|statement= Любое натуральное число представимо в виде суммы <tex dpi = 120> O(\log{N}) </tex> различных чисел Леонардо.
 +
}}
 +
 
 +
{{Утверждение
 +
|statement= <tex dpi = 120> L(n) = 2 \cdot F(n + 1) - 1 </tex>, где <tex dpi = 120> F(n + 1) </tex> {{---}} <tex dpi 120> (n + 1) </tex>-ое число Фибоначчи.
 +
|proof= Это утверждение доказывается по индукции. База: <tex dpi =120> L(0) = 2 \cdot F(1) - 1 = 1 </tex>. Пусть для <tex dpi = 120> n </tex> первых чисел это равенство выполняется. Делаем индуктивный переход: <tex dpi =120> L(n + 1) = L(n) + L(n - 1) + 1 = 2 \cdot F(n + 1) - 1 + 2 \cdot F(n) - 1 + 1 = 2 \cdot F(n + 2) - 1 </tex>. Утверждение доказано.  
 
}}
 
}}
  
Строка 16: Строка 28:
 
|definition =
 
|definition =
 
'''''K-ая куча Леонардо''''' — это двоичное дерево с количеством вершин <tex dpi = 120> L(k) </tex>, удовлетворяющее следующим условиям:
 
'''''K-ая куча Леонардо''''' — это двоичное дерево с количеством вершин <tex dpi = 120> L(k) </tex>, удовлетворяющее следующим условиям:
* Число, записанное в корне не меньше чисел в поддеревьях
+
* число, записанное в корне, не меньше чисел в поддеревьях,
* Левым поддеревом является <tex dpi = 120> (k-1) </tex>-я куча Леонардо
+
* левым поддеревом является <tex dpi = 120> (k-1) </tex>-я куча Леонардо,
* Правым — <tex dpi = 120> (k-2) </tex>-я куча Леонардо
+
* правым — <tex dpi = 120> (k-2) </tex>-я куча Леонардо.
  
 
}}
 
}}
[[Файл:leonardo-heap.png|600px|thumb|right|Пример последовательности куч с указанными размерами куч]]
+
Можно заметить, что куча Леонардо очень похожа на [[Биномиальная куча|биномиальную]].
Сортируемый массив делится на группу подмассивов. Каждый подмассив представляет собой структуру данных куча. Каждая куча имеет размер равный одному из чисел Леонардо. При этом левые элементы массива являются узлами самой большой возможной кучи. Оставшиеся элементы массива разбиваются на кучи по такому же жадному правилу. В дальнейшем эту группу подмассивов будем называть последовательность куч. При этом корни деревьев идут в порядке возрастания слева направо.
+
[[Файл:leonardo-heap.png|600px|thumb|right|Пример последовательности куч (список хранит номера чисел Леонардо, соответствующих размерам куч)]]
 +
Будем поддерживать следующий инвариант:
 +
* сортируемый массив делится на группу подмассивов,
 +
* каждый подмассив представляет собой структуру данных куча,
 +
* каждая куча имеет размер равный одному из чисел Леонардо,
 +
* размеры куч строго убывают слева направо,
 +
* при этом не существует двух куч, имеющих одинаковый размер,
 +
* значения ключей в корнях деревьев идут в порядке возрастания слева направо,
 +
* в самих кучах значение в детях меньше либо равно значению в родителе.
 +
В дальнейшем эту группу подмассивов будем называть последовательностью куч.  
 +
 
 +
===Алгоритм:===
 +
'''Шаг 0:''' В массиве записаны элементы, которые надо отсортировать.
  
При этом не существует двух куч, имеющих одинаковый размер. Так же никакие две кучи не будут иметь размер равным двум последовательным числам Леонардо. Исключением могут быть только две последние кучи.
+
'''Шаг 1:''' Превращение массива в последовательность куч.
Если мы будем использовать подряд две кучи размерностью <tex dpi = 120> L(x) </tex> и <tex dpi = 120> L(x+1) </tex>, то их можно будет заменить одной – размерностью <tex dpi = 120> L(x+2) </tex>.
 
  
'''Алгоритм состоит из двух стадий:'''
+
'''Шаг 2:''' Пока последовательность куч не пустая, достаем максимальный элемент (это всегда корень самой правой кучи) и восстанавливаем порядок куч, который мог измениться.
* Конструирование последовательности куч
 
* Пока последовательность куч не пустая достаем максимальный элемент (это всегда корень самой правой кучи) и восстанавливаем порядок куч, который мог измениться.
 
  
 
==Операции над последовательностью куч==
 
==Операции над последовательностью куч==
Необходимы две операции: увеличение последовательности куч путём добавления элемента справа и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности куч.
+
При конструировании последовательности куч будем по очереди вставлять в конец новые элементы, а при получении отсортированного массива {{---}} удалять максимальный элемент из последовательности. Следовательно, нам необходимы две операции: увеличение последовательности куч путём добавления элемента справа (будем считать, что в начале последовательности располагаются кучи максимального размера) и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности.
 +
 
 +
Чтобы быстро обращаться к кучам, будем хранить список их длин. Зная индекс корня некоторой кучи и её длину, можно найти индекс корня кучи слева от неё. Чтобы искать индексы детей вершины, надо воспользоваться свойством кучи Леонардо, что левым поддеревом является <tex dpi = 120> (n - 1) </tex>-ая, а правым является <tex dpi = 120> (n - 2) </tex>-ая куча Леонардо. Для хранения списка длин куч придется выделить <tex dpi = 120> O(\log{N}) </tex> дополнительной памяти.
 +
 
 
===Вставка элемента===
 
===Вставка элемента===
 +
[[Файл:add-example.png|470px|thumb|right|Пример вставки элемента (без просеивания вниз)]]
 +
[[Файл:Leonardo-heap-2.png|470px|thumb|right|Вставка в последовательность куч, показанную выше, числа 13. Далее будет сразу происходить просеивание внутри "зеленого" дерева Леонардо, так как корень соседнего дерева меньше, чем дети корня "зелёного" дерева.]]
 +
При добавлении в последовательность нового элемента возможны две ситуации:
 +
 
* Если две последние кучи имеют размеры <tex dpi = 120> L(x + 1) </tex> и <tex dpi = 120> L(x) </tex> (двух последовательных чисел Леонардо), новый элемент становится корнем кучи большего размера, равного <tex dpi = 120> L(x+2) </tex>. Для неё свойство кучи необязательно.
 
* Если две последние кучи имеют размеры <tex dpi = 120> L(x + 1) </tex> и <tex dpi = 120> L(x) </tex> (двух последовательных чисел Леонардо), новый элемент становится корнем кучи большего размера, равного <tex dpi = 120> L(x+2) </tex>. Для неё свойство кучи необязательно.
* Если размеры двух последних куч не равны двум последовательным числам Леонардо, новый элемент образует новую кучу размером 1. Этот размер полагается равным <tex dpi = 120> L(1) </tex>, кроме случая, когда крайняя правая куча уже имеет размер <tex dpi = 120> L(1) </tex>, тогда размер новой одноэлементной кучи полагают равным <tex dpi = 120> L(0) </tex>.
+
* Если размеры двух последних куч не равны двум последовательным числам Леонардо, новый элемент образует новую кучу размером <tex dpi = 120> 1 </tex>. Этот размер полагается равным <tex dpi = 120> L(1) </tex>, кроме случая, когда крайняя правая куча уже имеет размер <tex dpi = 120> L(1) </tex>, тогда размер новой одноэлементной кучи полагают равным <tex dpi = 120> L(0) </tex>.
После этого должно быть восстановлено выполнение свойств кучи и последовательности куч, что, как правило, достигается при помощи разновидности [[Сортировка вставками|сортировки вставками]]:
+
После этого необходимо восстановить свойства кучи и последовательности куч, что, как правило, достигается при помощи разновидности [[Сортировка вставками|сортировки вставками]] (см. ниже псевдокод):
 
# Крайняя правая куча (сформированная последней) считается «текущей» кучей.
 
# Крайняя правая куча (сформированная последней) считается «текущей» кучей.
# Пока слева от неё есть куча и значение её корня больше значения текущего корня и обоих корней куч-потомков:
+
# Пока слева от неё есть куча, и значение её корня больше значения текущего корня и обоих корней куч-потомков:
#* Меняются местами новый корень и корень кучи слева (что не нарушит свойство для текущей кучи). Эта куча становится текущей.
+
#* Меняются местами новый корень и корень кучи слева (это гарантирует выполнение инварианта для текущей кучи). И куча, с которой произошел обмен, становится текущей.
# Выполняется «просеивание», чтобы выполнялось свойство кучи:
+
# Потом выполняется «просеивание» кучи, на которой остановилась сортировка корней, чтобы гарантировать выполнение инварианта кучи:
#* Пока размер текущей кучи больше 1 и значение корня любой из куч-потомков больше значения корня текущей кучи:
+
#* Пока размер текущей кучи больше <tex dpi = 120> 1 </tex>, и значение корня любой из куч-потомков больше значения корня текущей кучи:
 
#** Меняются местами наибольший по значению корень кучи-потомка и текущий корень. Куча-потомок становится текущей кучей.
 
#** Меняются местами наибольший по значению корень кучи-потомка и текущий корень. Куча-потомок становится текущей кучей.
Операция просеивания значительно упрощена благодаря использованию чисел Леонардо, так как каждая куча либо будет одноэлементной, либо будет иметь двух потомков. Нет нужды беспокоиться об отсутствии одной из куч-потомков.
+
Просеивание в куче Леонардо сильно упрощено, так как каждая куча будет иметь либо двух потомков, либо ноль. Нет нужды беспокоиться об отсутствии одной из куч-потомков.
  
Так как в последовательности <tex dpi = 120> O(log N) </tex> куч и просеивание можно выполнить за <tex dpi = 120> O(log N) </tex>, то время вставки равно:
+
Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то модификация сортировки вставками будет работать за <tex dpi = 120> O(\log{N}) </tex>. Просеивание тоже выполняется за <tex dpi = 120> O(\log{N}) </tex>, тогда в итоге операция вставки выполняется за:
<tex dpi = 120> O(log N) + O(log N) = O(log N) </tex>.
+
<tex dpi = 120> O(\log{N}) + O(\log{N}) = O(\log{N}) </tex>.
  
 
=== Уменьшение последовательности куч путём удаления элемента справа ===
 
=== Уменьшение последовательности куч путём удаления элемента справа ===
Если размер крайней правой кучи равен 1 (то есть <tex dpi = 120> L(1) </tex> или <tex dpi = 120> L(0) </tex>), эта куча просто удаляется.
+
Если размер крайней правой кучи равен <tex dpi = 120> 1 </tex> (то есть <tex dpi = 120> L(1) </tex> или <tex dpi = 120> L(0) </tex>), эта куча просто удаляется.
В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства последовательности куч (т.е. что корни деревьев идут в порядке возрастания слева направо), сначала для левой кучи, затем — для правой.
+
В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства последовательности куч (т.е. корни деревьев идут в порядке возрастания слева направо), сначала для левой кучи, затем — для правой.
  
Так как в последовательности <tex dpi = 120> O(log N) </tex> куч, то восстановление свойства последовательности выполняется за <tex dpi = 120> O(log N) </tex>.
+
Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч, то восстановление свойства последовательности выполняется за <tex dpi = 120> O(\log{N}) </tex>.
 +
 
 +
===Восстановление свойств последовательности===
 +
 
 +
Пусть нам надо восстановить инвариант последовательности куч. Будем считать, что функции <tex>\mathrm{prev}</tex> (возвращает индекс корня ближайшей слева кучи), <tex>\mathrm{left}</tex> (возвращает индекс левого сына), <tex>\mathrm{right}</tex> (возвращает индекс правого сына) уже реализованы. В функцию <tex>\mathrm{ensureSequence}</tex> передается индекс корня кучи, с которой начинаем восстановление.
 +
<code>
 +
'''function''' ensureSequence(i: '''int'''):
 +
  j = prev(i) <font color = "green">// j - индекс корня соседней кучи</font>
 +
  '''while''' A[j] > A[i] '''and''' A[j] > A[left(i)] '''and''' A[j] > A[right(i)]
 +
    swap(A[j], A[i])
 +
    i = j
 +
    j = prev(i)
 +
  siftDown(i)
 +
</code>
  
 
==Сложность==  
 
==Сложность==  
Во время построения последовательности куч <tex dpi = 120> O(N) </tex> раз выполняется вставка элемента. И потом ещё <tex dpi = 120> O(N) </tex> раз выполняется удаление элемента при процедуре получения отсортированного массива. Таким образом сложность плавной сортировки составляет <tex dpi = 120> O(N log N) </tex>.
 
  
Однако если подать на вход плавной сортировке уже отсортированный массив асимптотика будет составлять <tex dpi = 120> O(N) </tex>. Дело в том, что во время процедуры получения последовательности куч мы всегда будем вставлять элемент, который больше остальных уже находящихся в последовательности. Поэтому восстановление свойства последовательности будет выполняться за <tex dpi = 120> O(1) </tex> (так как алгоритм только посмотрит на корень соседней кучи, а просеивание закончится сразу потому что новый элемент будет больше своих детей). Операция получения и удаления максимального элемента будет тоже выполняться за <tex dpi = 120> O(1) </tex>, потому что в силу построения в корнях куч-детей будут новые максимальные элементы и следовательно восстановление свойства последовательности закончится на просмотре корня соседней кучи. В итоге, так как алгоритм <tex dpi =120> O(N) </tex> раз вставляет, а потом и удаляет элементы, получается асимптотика <tex dpi = 120> O(N) </tex>.
+
===Построение последовательности===
 +
Последовательность куч получается при вставке элементов массива по очереди в эту самую последовательность. Получаем время работы <tex dpi = 120> O(N \log{N}) </tex>.
 +
 
 +
===Получение отсортированного массива===
 +
Так как удаление максимального элемента из последовательности выполняется за <tex dpi = 120> O(\log{N}) </tex>, то время работы сортировки составляет <tex dpi = 120> O(N\log{N}) </tex>.
 +
 
 +
===Лучший случай===
 +
Однако если подать на вход плавной сортировке уже отсортированный массив, асимптотика будет составлять <tex dpi = 120> O(N) </tex>. Дело в том, что:
 +
*Операция добавления элемента последовательности на таком примере будет выполняться за <tex dpi = 120> O(1) </tex>, из-за того, что в конец будет добавляться максимальный элемент и просеивание будет сразу останавливаться.
 +
*Операция получения и удаления максимального элемента будет также выполняться за <tex dpi = 120> O(1) </tex>, потому что в силу построения в корнях куч-детей будут новые максимальные элементы и следовательно восстановление свойства последовательности закончится на просмотре корня соседней кучи.
 +
В итоге на таком примере получается асимптотика <tex dpi = 120> O(N) </tex>.
  
 
===Достоинства===
 
===Достоинства===
* худшее время работы -- <tex dpi = 120> O(N log N) </tex>
+
* худшее время работы {{---}} <tex dpi = 120> O(N\log{N}) </tex>,
* время работы в случае, когда подается отсортированный массив -- <tex dpi = 120> O(N) </tex>
+
* время работы в случае, когда подается отсортированный массив {{---}} <tex dpi = 120> O(N) </tex>.
  
 
===Недостатки===
 
===Недостатки===
* не является устойчивой
+
* не является устойчивой,
* требует <tex dpi = 120> O(N) </tex> дополнительной памяти для хранения последовательности куч
+
* требует <tex dpi = 120> O(\log{N}) </tex> дополнительной памяти для хранения длин куч в последовательности. Однако с помощью некоторых модификаций расходы на дополнительную память можно сократить до <tex dpi 120> O(1) </tex>.
 +
 
 +
===Связь с быстрой сортировкой===
 +
На практике, когда реализуют алгоритм быстрой сортировки, пытаются улучшить асимптотику в худшем случае. Для этого заводится некоторый лимит глубины рекурсии, при превышении которого запускают другую сортировку. Так реализована сортировка в стандартной библиотеке языка С++. Часто при превышении порога глубины рекурсии используют сортировку кучей. Замена неё на плавную сортировку могла бы улучшить время работы на некоторых тестах, так как после нескольких итераций быстрой сортировки массив окажется почти отсортированным, а на таких массивах время работы плавной сортировки приближается к линейному. Хотя итоговой линейной асимптотики достичь всё равно не получится по [[Теорема о нижней оценке для сортировки сравнениями | теореме о нижней оценке]].
 +
 
 +
==См. также==
 +
* [[Сортировка кучей|Сортировка кучей]]
 +
* [[Быстрая сортировка|Быстрая сортировка]]
 +
 
 +
==Примечания==
 +
 
 +
<references />
  
 
==Источники информации==
 
==Источники информации==
* [https://en.wikipedia.org/wiki/Smoothsort Wikipedia -- Smoothsort]
+
* [https://en.wikipedia.org/wiki/Smoothsort Wikipedia {{---}} Smoothsort]
 
* [http://www.keithschwarz.com/smoothsort/ Smoothsort Demystified]
 
* [http://www.keithschwarz.com/smoothsort/ Smoothsort Demystified]
* [http://habrahabr.ru/post/133996/ Хабрахабр -- И снова про сортировки]
+
* [http://habrahabr.ru/post/133996/ Хабрахабр {{---}} И снова про сортировки]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
+
[[Категория: Сортировка]]
 +
[[Категория: Сортировки на сравнениях]]

Текущая версия на 19:26, 4 сентября 2022

Плавная сортировка (англ. Smooth sort) — алгоритм сортировки, модификация сортировки кучей, разработанный Э. Дейкстрой. Как и пирамидальная сортировка, в худшем случае работает за время [math] \Theta(N\log{N}) [/math]. Преимущество плавной сортировки в том, что её время работы приближается к [math] O(N) [/math], если входные данные частично отсортированы, в то время как у сортировки кучей время работы не зависит от состояния входных данных.

Основная идея

Разовьём идею пирамидальной сортировки. Для этого используем не двоичную кучу, а специальную, полученную с помощью чисел Леонардо[1], которые задаются следующим образом:

[math] L(n) = \begin{cases} 1 & \mathrm{if}\ n = 0, \\ 1 & \mathrm{if}\ n = 1, \\ L(n-1)+L(n-2)+1 & \mathrm{if}\ n \gt 1. \\ \end{cases} [/math]

Вот первые несколько членов этой последовательности: [math] 1, 1, 3, 5, 9, 15, 25, 41, ... [/math]

Утверждение:
Любое натуральное число представимо в виде суммы [math] O(\log{N}) [/math] различных чисел Леонардо.
Утверждение:
[math] L(n) = 2 \cdot F(n + 1) - 1 [/math], где [math] F(n + 1) [/math][math] (n + 1) [/math]-ое число Фибоначчи.
[math]\triangleright[/math]
Это утверждение доказывается по индукции. База: [math] L(0) = 2 \cdot F(1) - 1 = 1 [/math]. Пусть для [math] n [/math] первых чисел это равенство выполняется. Делаем индуктивный переход: [math] L(n + 1) = L(n) + L(n - 1) + 1 = 2 \cdot F(n + 1) - 1 + 2 \cdot F(n) - 1 + 1 = 2 \cdot F(n + 2) - 1 [/math]. Утверждение доказано.
[math]\triangleleft[/math]


Определение:
K-ая куча Леонардо — это двоичное дерево с количеством вершин [math] L(k) [/math], удовлетворяющее следующим условиям:
  • число, записанное в корне, не меньше чисел в поддеревьях,
  • левым поддеревом является [math] (k-1) [/math]-я куча Леонардо,
  • правым — [math] (k-2) [/math]-я куча Леонардо.

Можно заметить, что куча Леонардо очень похожа на биномиальную.

Пример последовательности куч (список хранит номера чисел Леонардо, соответствующих размерам куч)

Будем поддерживать следующий инвариант:

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

В дальнейшем эту группу подмассивов будем называть последовательностью куч.

Алгоритм:

Шаг 0: В массиве записаны элементы, которые надо отсортировать.

Шаг 1: Превращение массива в последовательность куч.

Шаг 2: Пока последовательность куч не пустая, достаем максимальный элемент (это всегда корень самой правой кучи) и восстанавливаем порядок куч, который мог измениться.

Операции над последовательностью куч

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

Чтобы быстро обращаться к кучам, будем хранить список их длин. Зная индекс корня некоторой кучи и её длину, можно найти индекс корня кучи слева от неё. Чтобы искать индексы детей вершины, надо воспользоваться свойством кучи Леонардо, что левым поддеревом является [math] (n - 1) [/math]-ая, а правым является [math] (n - 2) [/math]-ая куча Леонардо. Для хранения списка длин куч придется выделить [math] O(\log{N}) [/math] дополнительной памяти.

Вставка элемента

Пример вставки элемента (без просеивания вниз)
Вставка в последовательность куч, показанную выше, числа 13. Далее будет сразу происходить просеивание внутри "зеленого" дерева Леонардо, так как корень соседнего дерева меньше, чем дети корня "зелёного" дерева.

При добавлении в последовательность нового элемента возможны две ситуации:

  • Если две последние кучи имеют размеры [math] L(x + 1) [/math] и [math] L(x) [/math] (двух последовательных чисел Леонардо), новый элемент становится корнем кучи большего размера, равного [math] L(x+2) [/math]. Для неё свойство кучи необязательно.
  • Если размеры двух последних куч не равны двум последовательным числам Леонардо, новый элемент образует новую кучу размером [math] 1 [/math]. Этот размер полагается равным [math] L(1) [/math], кроме случая, когда крайняя правая куча уже имеет размер [math] L(1) [/math], тогда размер новой одноэлементной кучи полагают равным [math] L(0) [/math].

После этого необходимо восстановить свойства кучи и последовательности куч, что, как правило, достигается при помощи разновидности сортировки вставками (см. ниже псевдокод):

  1. Крайняя правая куча (сформированная последней) считается «текущей» кучей.
  2. Пока слева от неё есть куча, и значение её корня больше значения текущего корня и обоих корней куч-потомков:
    • Меняются местами новый корень и корень кучи слева (это гарантирует выполнение инварианта для текущей кучи). И куча, с которой произошел обмен, становится текущей.
  3. Потом выполняется «просеивание» кучи, на которой остановилась сортировка корней, чтобы гарантировать выполнение инварианта кучи:
    • Пока размер текущей кучи больше [math] 1 [/math], и значение корня любой из куч-потомков больше значения корня текущей кучи:
      • Меняются местами наибольший по значению корень кучи-потомка и текущий корень. Куча-потомок становится текущей кучей.

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

Так как в последовательности [math] O(\log{N}) [/math] куч, то модификация сортировки вставками будет работать за [math] O(\log{N}) [/math]. Просеивание тоже выполняется за [math] O(\log{N}) [/math], тогда в итоге операция вставки выполняется за: [math] O(\log{N}) + O(\log{N}) = O(\log{N}) [/math].

Уменьшение последовательности куч путём удаления элемента справа

Если размер крайней правой кучи равен [math] 1 [/math] (то есть [math] L(1) [/math] или [math] L(0) [/math]), эта куча просто удаляется. В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства последовательности куч (т.е. корни деревьев идут в порядке возрастания слева направо), сначала для левой кучи, затем — для правой.

Так как в последовательности [math] O(\log{N}) [/math] куч, то восстановление свойства последовательности выполняется за [math] O(\log{N}) [/math].

Восстановление свойств последовательности

Пусть нам надо восстановить инвариант последовательности куч. Будем считать, что функции [math]\mathrm{prev}[/math] (возвращает индекс корня ближайшей слева кучи), [math]\mathrm{left}[/math] (возвращает индекс левого сына), [math]\mathrm{right}[/math] (возвращает индекс правого сына) уже реализованы. В функцию [math]\mathrm{ensureSequence}[/math] передается индекс корня кучи, с которой начинаем восстановление.

function ensureSequence(i: int):
  j = prev(i) // j - индекс корня соседней кучи
  while A[j] > A[i] and A[j] > A[left(i)] and A[j] > A[right(i)]
    swap(A[j], A[i])
    i = j
    j = prev(i)
  siftDown(i)

Сложность

Построение последовательности

Последовательность куч получается при вставке элементов массива по очереди в эту самую последовательность. Получаем время работы [math] O(N \log{N}) [/math].

Получение отсортированного массива

Так как удаление максимального элемента из последовательности выполняется за [math] O(\log{N}) [/math], то время работы сортировки составляет [math] O(N\log{N}) [/math].

Лучший случай

Однако если подать на вход плавной сортировке уже отсортированный массив, асимптотика будет составлять [math] O(N) [/math]. Дело в том, что:

  • Операция добавления элемента последовательности на таком примере будет выполняться за [math] O(1) [/math], из-за того, что в конец будет добавляться максимальный элемент и просеивание будет сразу останавливаться.
  • Операция получения и удаления максимального элемента будет также выполняться за [math] O(1) [/math], потому что в силу построения в корнях куч-детей будут новые максимальные элементы и следовательно восстановление свойства последовательности закончится на просмотре корня соседней кучи.

В итоге на таком примере получается асимптотика [math] O(N) [/math].

Достоинства

  • худшее время работы — [math] O(N\log{N}) [/math],
  • время работы в случае, когда подается отсортированный массив — [math] O(N) [/math].

Недостатки

  • не является устойчивой,
  • требует [math] O(\log{N}) [/math] дополнительной памяти для хранения длин куч в последовательности. Однако с помощью некоторых модификаций расходы на дополнительную память можно сократить до [math] O(1) [/math].

Связь с быстрой сортировкой

На практике, когда реализуют алгоритм быстрой сортировки, пытаются улучшить асимптотику в худшем случае. Для этого заводится некоторый лимит глубины рекурсии, при превышении которого запускают другую сортировку. Так реализована сортировка в стандартной библиотеке языка С++. Часто при превышении порога глубины рекурсии используют сортировку кучей. Замена неё на плавную сортировку могла бы улучшить время работы на некоторых тестах, так как после нескольких итераций быстрой сортировки массив окажется почти отсортированным, а на таких массивах время работы плавной сортировки приближается к линейному. Хотя итоговой линейной асимптотики достичь всё равно не получится по теореме о нижней оценке.

См. также

Примечания

Источники информации