Плавная сортировка14.04.2020 10:04

Продолжаем погружение в разнообразные кучи.

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

Многие слыхали про эту сортировку, однако мало кто знает как именно она работает. Сегодня увидим, что ничего сложного в ней нет.

Метод изобрёл легендарный Эдсгер Дейкстра. Помимо многочисленных ярчайших достижений в теории алгоритмов, он также является автором такого остроумного высказывания:

«Студентов, ранее изучавших Бейсик, практически невозможно обучить хорошему программированию. Как потенциальные программисты они подверглись необратимой умственной деградации.»

Надеюсь, не будет кощунством, что анимация в статье создана с помощью VBA:-)

Статья написана при поддержке компании EDISON.
Мы занимаемся портированием и миграцией программного обеспечения, а также разработкой мобильных приложений Android и iOS.
Мы очень любим теорию алгоритмов! ;-)

Сортировка кучей сама по себе очень хороша, так как её сложность по времени O (n log n) вне зависимости от данных. Чтобы из себя не представлял массив, сложность heapsort никогда не деградирует до O (n2), что может приключиться, к примеру, с быстрой сортировкой. Обратной стороной медали является то, что сортировку бинарной кучей нельзя и ускорить, сложности O (n) ожидать также не приходится (а вот та же быстрая сортировка, при определённых условиях может достигать таких показателей).

В общем, на повестке дня стоял вопрос: можно ли исхитриться так, чтобы временна́я сложность сортировка кучей, с одной стороны, была не ниже чем O (n log n), но при благоприятном раскладе (в частности, если обрабатывается почти отсортированный массив) повышалась до O (n)?

Этим вопросом лично занялся сам Эдсгер Дейкстра, который выяснил, что да, можно.

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

Что не так с бинарной кучей

Давайте взглянем, как heapsort сортирует почти упорядоченный массив и разберёмся, почему этот алгоритм не обрабатывает быстрее такие входящие данные.

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

Второй замедляющий фактор, который не так очевиден — стандартная двоичная куча сама по себе всегда является сбалансированным деревом. В случае изначально упорядоченных данных это играет в минус. Если в первоначальном массиве рандомные данные — то они равномерно распределяются в сбалансированном дереве и многократная просейка проходится по всем веткам примерно одинаковое число раз. Для почти упорядоченных данных, более желательно несбалансированное дерево — в этом случае данные на той части массива, которые соответствуют более длинным веткам дерева просейка будет обрабатывать реже, чем другие.

Числа Леонардо

Чтобы решить обе проблемы, Дейкстра предложил использовать специальные двоичные кучи, построенные на числах Леонардо.

Числа Леонардо — это почти как числа Фибоначчи, но только лучше.
Ряд чисел Леонардо задаётся рекурретно:

L0 = 1
L1 = 1
Ln = Ln − 1 + Ln − 2 + 1

Первые 20 чисел Леонардо:
1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529

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

Это в нашем случае очень полезно. Массив из n элементов не всегда можно представить в виде одной кучи Леонардо (если n не является числом Леонардо). Но зато, любой массив всегда можно разделить на несколько подмассивов, которые будкт соответствовать разным числам Леонардо, т.е. представлять из себя кучи разного порядка.

Вот пример массива из 21-го элемента, состоящий из трёх леонардовых куч. В каждой из куч количество узлов соответствует какому-либо числу Леонардо.

Важные моменты, которые следует знать:

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

Построение кучи куч и её демонтаж

В рекуррентной формуле для чисел Леонардо
Ln = Ln − 1 + Ln − 2 + 1
очень радует единичка в конце.

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

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

На втором этапе алгоритма происходит обратный процесс — мы разбираем кучи. Если в куче удалить корень, то мы получим две кучи поменьше, соответствующие двум предыдущим числам Леонардо. Это можно сделать, поскольку:
Ln − 1 = Ln − 1 + Ln − 2

В числах Фибоначчи такой полезной единички нет, поэтому мы и не используем фибоначчиеву кучу.

Плавная сортировка :: Smoothsort

Итоговый алгоритм:

I. Создаём из массива кучу леонардовых куч, каждая из которых является сортирующим деревом.
- I.1. Перебираем элементы массива слева-направо.
- II.1. Проверяем, можно ли с помощью текущего элемента объединить две крайние слева кучи в уже имеющейся куче леонардовых куч:
  - II.1.а. Если да, то объединяем две крайние слева кучи в одну, текущий элемент становится корнем этой кучи, делаем просейку для объединённой кучи.
  - II.1.б. Если нет, то добавляем текущий элемент в качестве новой кучи (состоящей пока из одного узла) в имеющуюся кучу леонардовых куч.
II. Извлекаем из куч текущие максимальные элементы, которые перемещаем в конец неотсортированной части массива:
- II.1. Ищем максимумы в леонардовых кучах. Так как на предыдущем этапе для куч постоянно делалась просейка, максимумы находятся в корнях этих куч.
- II.2. Найденный максимум (который является корнем одной из куч) меняем местами с последним элементом массива (который является корнем самой последней кучи).
- II.3. После этого обмена куча, в которой был найден максимум перестала быть сортирующим деревом. Поэтому делаем для неё просейку.
- II.4. В последней куче удаляем корень (в которой находится текущий максимум), в результате чего эта куча распадается на две кучи поменьше.
- II.5. После перемещения максимального элемента в конец, отсортированная часть массива увеличилась, а неотсортированная часть уменьшилась. Повторяем пункты II.1-II.4 для оставшейся неотсортированной части массива.

Пример реализации на Python

import random

def smoothsort(lst):

    #Вычислим необходимое количество чисел Леонардо
    leo_nums = leonardo_numbers(len(lst))


    #Куча будет храниться в виде списка деревьев Леонардо
    heap = []

    # Создание первоначальной кучи
    # Очередной элемент или объединяет две предыдущие кучи
    # или добавляет новую кучу из одного узла
    for i in range(len(lst)):
        if len(heap) >= 2 and heap[-2] == heap[-1] + 1:
            heap.pop()
            heap[-1] += 1
        else:
            if len(heap) >= 1 and heap[-1] == 1:
                heap.append(0)
            else:
                heap.append(1)
        restore_heap(lst, i, heap, leo_nums)

    #Разбираем кучу куч
    for i in reversed(range(len(lst))):
        if heap[-1] < 2:
            heap.pop()
        else:
            k = heap.pop()
            t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
            heap.append(k_l)
            restore_heap(lst, t_l, heap, leo_nums)
            heap.append(k_r)
            restore_heap(lst, t_r, heap, leo_nums)

# Генерация чисел Леонардо, не превышающих количество элементов массива
def leonardo_numbers(hi):

    a, b = 1, 1
    numbers = []
    while a <= hi:
        numbers.append(a)
        a, b = b, a + b + 1
    return numbers

# Восстановление кучи после слияния куч или удаления корня
def restore_heap(lst, i, heap, leo_nums):
    
    # Модифицированная сортировка вставками для корней куч
    
    current = len(heap) - 1
    k = heap[current]

    while current > 0:
        j = i - leo_nums[k]
        if (lst[j] > lst[i] and
            (k < 2 or lst[j] > lst[i-1] and lst[j] > lst[i-2])):
            lst[i], lst[j] = lst[j], lst[i]
            i = j
            current -= 1
            k = heap[current]
        else:
            break

    # Просейка
    
    while k >= 2:
        t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
        if lst[i] < lst[t_r] or lst[i] < lst[t_l]:
            if lst[t_r] > lst[t_l]:
                lst[i], lst[t_r] = lst[t_r], lst[i]
                i, k = t_r, k_r
            else:
                lst[i], lst[t_l] = lst[t_l], lst[i]
                i, k = t_l, k_l
        else:
            break

# При удалении корня куча делится на две меньшие кучи,
# соответствующие двум предыдущим числами Леонардо
def get_child_trees(i, k, leo_nums):

    t_r, k_r = i - 1, k - 2
    t_l, k_l = t_r - leo_nums[k_r], k - 1
    return t_r, k_r, t_l, k_l

# Основная процедура
def main(n):
    lst = list(range(n))
    random.shuffle(lst)
    print(lst)
    smoothsort(lst)
    print(lst)

Сложность по времени

Если мы возьмём на вход почти упорядоченный массив, то визуализация показывает, за счёт чего такой массив обрабатывается заметно быстрее.

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

Давайте прикинем общую временну́ю сложность.

На первом этапе мы перебираем n элементов, добавляя его в уже имеющиеся слева кучи. Само добавление в кучу обходится в O (1), но затем для кучи нужно сделать просейку. В упорядоченных данных неглубокая просейка часто обходится O (1) для одного добавляемоего в кучу элемента. В неупорядоченных данных просейка для каждого добавления обходится в O (log n), так как как из-за рандома просейке приходится проходить уровни дерева часто до самого низа.

Поэтому, на первом этапе наилучшая сложность по времени:
для почти упорядоченных данных — O (n),
для рандомных данных — O (n log n).

Для второго этапа ситуация аналогичная. При обмене очередного максимума опять нужно просеять кучу, в корне которой он находился. И показатели просейки для упорядоченных и неупорядоченных данных будут различные.

На втором этапе наилучшая сложность по времени такая же как и на первом:
для почти упорядоченных данных — O (n),
для рандомных данных — O (n log n).

Складывая временны́е сложности для первого и второго этапа:
для почти упорядоченных данных — O (2n) = O (n),
для рандомных данных — O (2 n log n) = O (n log n).

В общем, худшая и средняя временна́я сложность для плавной сортировки — O (n log n).
Дейкстра в своих выкладках (которыми я не стану вас утомлять) доказал, что лучшая сложность плавно стремится к O (n) чем более упорядоченными будут входящие данные. Отсюда и название — плавная сортировка.

Сложность по дополнительной памяти

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

Сортировка биномиальной кучей :: Binomial heap sort

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

В принципе, можно сделать плавную сортировку, работающую на основе биномов:

Будет ли она работать быстрее? Вряд ли. Биномиальная куча не является двоичной, а в прошлой статье мы выяснили, что увеличение числа потомков не ускоряет, а замедляет просейку. Кроме того можно заметить, что у биномиальной кучи более длинные ответвления, из-за чего соседние упорядоченные области массива будут несколько медленнее соединяться друг с другом.

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

Трейлер следующей серии

Впрочем, даже если для плавной сортировке биномиальная куча не лучший вариант, не стоит её окончательно списывать в утиль.

Если биномиальное дерево слегка видоизменить и применить для его обхода совершенно другие (весьма смелые) идеи, то получится оригинальный и эффективный алгоритм, имеющий собственные преимущества. О чём мы в следующий раз и поговорим.

Ссылки

Smooth / Плавность

Числа Леонардо, Binomial Heap / Биномиальная куча

Статьи серии:

В приложение AlgoLab добавлена сегодняшняя плавная сортировка. А также бонусом — и сортировка биномиальной кучей. Так что, кому хочется лично погонять данные на куче куч — обновите excel-файл с макросами.