Heapsort

Heapsort – пирамидальная сортировка. Временная сложность алгоритма – O(n log n), шустрый да? Я бы назвал эту сортировку – сортировкой падающих камушков. Объяснять её, как мне кажется, проще всего визуально.

На вход подается список цифр, например:
5, 0, 7, 2, 3, 9, 4

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

Сделаем двоичное дерево:
⠀⠀5
⠀0⠀7
2 3 9 4

Если долго смотреть на пирамидку, то можно увидеть что это просто числа из массива, идущие друг за другом, количество элементов в каждом этаже умножается на два.

Далее начинается самое интересное, отсортируем пирамидку снизу вверх, методом падающих камушков (heapify). Сортировку можно было бы начинать с последнего этажа (2 3 9 4 ), но смысла нет т.к. нет этажа ниже, куда можно было бы упасть.

Поэтому начинаем ронять элементы с предпоследнего этажа (0 7)
⠀⠀5
⠀0⠀7
2 3 9 4

Первый элемент для падения выбирается справа, нашем случае это 7, далее смотрим что под ним, а под ним 9 и 4, девятка больше четверки, так еще и девятка больше семерки! Роняем 7 на 9, а 9 поднимаем на место 7.
⠀⠀5
⠀0⠀9
2 3 7 4

Далее понимаем что семерке падать ниже некуда, переходим к числу 0 которое находится на предпоследнем этаже слева:
⠀⠀5
0⠀9
2 3 7 4

Смотрим что под ним – 2 и 3, два меньше трех, три больше нуля, поэтому меняем ноль и три местами:
⠀⠀5
⠀3⠀9
2 0 7 4

Когда добрались до конца этажа – переходите на этаж выше и роняйте там всё, если сможете.
В итоге получится структура данных – куча (heap), а именно max heap, т.к. наверху самый большой элемент:
⠀⠀9
⠀3⠀7
2 0 5 4

Если вернуть в представление массива, то получится список:
[9, 3, 7, 2, 0, 5, 4]

Из этого можно сделать вывод, что поменяв местами первый и последний элемент, мы получим первое число в окончательной отсортированной позиции, а именно 9 должна стоять в конце отсортированного списка, меняем местами:
[4, 3, 7, 2, 0, 5, 9]

Посмотрим на бинарное дерево:
⠀⠀4
⠀3⠀7
2 0 5 9

Получилась ситуация при которой нижняя часть древа отсортирована, нужно лишь уронить 4 до корректной позиции, повторяем алгоритм, но не учитываем уже отсортированные числа, а именно 9:
⠀⠀4
⠀3⠀7
2 0 5 9

⠀⠀7
⠀3⠀4
2 0 5 9

⠀⠀7
⠀3⠀5
2 0 4 9

Получилось что мы, уронив 4, подняли следующее после 9 самое больше число – 7. Меняем местами последнее неотсортированное число (4) и самое больше число (7)
⠀⠀4
⠀3⠀5
2 0 7 9

Получилось что теперь мы имеем два числа в корректной окончательной позиции:
4, 3, 5, 2, 0, 7, 9

Далее повторяем алгоритм сортировки, игнорируя уже отсортированные, в итоге получим кучу вида:
⠀⠀0
⠀2⠀3
4 5 7 9

Или в виде списка:
0, 2, 3, 4, 5, 7, 9

Реализация

Алгоритм обычно разделяют на три функции:

  1. Создание кучи
  2. Алгоритм просеивания (heapify)
  3. Замена последнего неотсортированного элемента и первого

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

Пример Heapsort на Ruby:

DEMO = true

module Colors
    BLUE = "\033[94m"
    RED = "\033[31m"
    STOP = "\033[0m"
end

def heapsort(rawNumbers)
    numbers = rawNumbers.dup

    def swap(numbers, from, to)
        temp = numbers[from]
        numbers[from] = numbers[to]
        numbers[to] = temp
    end

    def heapify(numbers)
        count = numbers.length()
        lastParentNode = (count - 2) / 2

        for start in lastParentNode.downto(0)
            siftDown(numbers, start, count - 1)
            start -= 1 
        end

        if DEMO
            puts "--- heapify ends ---"
        end
    end

    def siftDown(numbers, start, rightBound)      
        cursor = start
        printBinaryHeap(numbers, cursor, rightBound)

        def calculateLhsChildIndex(cursor)
            return cursor * 2 + 1
        end

        def calculateRhsChildIndex(cursor)
            return cursor * 2 + 2
        end            

        while calculateLhsChildIndex(cursor) <= rightBound
            lhsChildIndex = calculateLhsChildIndex(cursor)
            rhsChildIndex = calculateRhsChildIndex(cursor)

            lhsNumber = numbers[lhsChildIndex]
            biggerChildIndex = lhsChildIndex

            if rhsChildIndex <= rightBound
                rhsNumber = numbers[rhsChildIndex]
                if lhsNumber < rhsNumber
                    biggerChildIndex = rhsChildIndex
                end
            end

            if numbers[cursor] < numbers[biggerChildIndex]
                swap(numbers, cursor, biggerChildIndex)
                cursor = biggerChildIndex
            else
                break
            end
            printBinaryHeap(numbers, cursor, rightBound)
        end
        printBinaryHeap(numbers, cursor, rightBound)
    end

    def printBinaryHeap(numbers, nodeIndex = -1, rightBound = -1)
        if DEMO == false
            return
        end
        perLineWidth = (numbers.length() * 4).to_i
        linesCount = Math.log2(numbers.length()).ceil()
        xPrinterCount = 1
        cursor = 0
        spacing = 3
        for y in (0..linesCount)
            line = perLineWidth.times.map { " " }
            spacing = spacing == 3 ? 4 : 3
            printIndex = (perLineWidth / 2) - (spacing * xPrinterCount) / 2
            for x in (0..xPrinterCount - 1)
                if cursor >= numbers.length
                    break
                end
                if nodeIndex != -1 && cursor == nodeIndex
                    line[printIndex] = "%s%s%s" % [Colors::RED, numbers[cursor].to_s, Colors::STOP]
                elsif rightBound != -1 && cursor > rightBound
                    line[printIndex] = "%s%s%s" % [Colors::BLUE, numbers[cursor].to_s, Colors::STOP]
                else
                    line[printIndex] = numbers[cursor].to_s
                end
                cursor += 1
                printIndex += spacing
            end
            print line.join()
            xPrinterCount *= 2           
            print "\n"            
        end
    end

    heapify(numbers)
    rightBound = numbers.length() - 1

    while rightBound > 0
        swap(numbers, 0, rightBound)   
        rightBound -= 1
        siftDown(numbers, 0, rightBound)     
    end

    return numbers
end

numbersCount = 14
maximalNumber = 10
numbers = numbersCount.times.map { Random.rand(maximalNumber) }
print numbers
print "\n---\n"

start = Time.now
sortedNumbers = heapsort(numbers)
finish = Time.now
heapSortTime = start - finish

start = Time.now
referenceSortedNumbers = numbers.sort()
finish = Time.now
referenceSortTime = start - finish

print "Reference sort: "
print referenceSortedNumbers
print "\n"
print "Reference sort time: %f\n" % referenceSortTime
print "Heap sort:      "
print sortedNumbers
print "\n"
if DEMO == false
    print "Heap sort time:      %f\n" % heapSortTime
else
    print "Disable DEMO for performance measure\n"
end

if sortedNumbers != referenceSortedNumbers
    puts "Validation failed"
    exit 1
else
    puts "Validation success"
    exit 0
end

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

Ссылки

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/heapsort/heapsort.rb

Источники

http://rosettacode.org/wiki/Sorting_algorithms/Heapsort
https://www.youtube.com/watch?v=LbB357_RwlY
https://habr.com/ru/company/otus/blog/460087/
https://ru.wikipedia.org/wiki/Пирамидальная_сортировка
https://neerc.ifmo.ru/wiki/index.php?title=Сортировка_кучей
https://wiki5.ru/wiki/Heapsort
https://wiki.c2.com/?HeapSort
https://ru.wikipedia.org/wiki/Дерево (структура данных)
https://ru.wikipedia.org/wiki/Куча (структура данных)
https://www.youtube.com/watch?v=2DmK_H7IdTo
https://www.youtube.com/watch?v=kU4KBD4NFtw
https://www.youtube.com/watch?v=DU1uG5310x0
https://www.youtube.com/watch?v=BzQGPA_v-vc
https://www.geeksforgeeks.org/array-representation-of-binary-heap/
https://habr.com/ru/post/112222/
https://www.cs.usfca.edu/~galles/visualization/BST.html
https://www.youtube.com/watch?v=EQzqHWtsKq4
https://medium.com/@dimko1/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-heapsort-796ba965018b
https://ru.wikibrief.org/wiki/Heapsort
https://www.youtube.com/watch?v=GUUpmrTnNbw