Пирамидальная сортировка была предложена Дж. Уильямсом в 1964 году. Является «умной» модификацией-синтезом сортировки выбором и пузырьковой сортировки. Среди достоинств алгоритма - высокая скорость, не требует дополнительной памяти. Из недостатков можно выделить то, что алгоритм сложен в реализации, является неустойчивым, на частично упорядоченных массивах работает так же долго, как и на хаотических.

Алгоритм сортировки

Пояснение

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

Алгоритм

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

Визуализация работы алгоритма

Код программы

Для реализации самой сортировки необходимо создать класс Heap. Этот класс должен содержать само дерево, а также определённые методы.

Сама пирамида хранится в списке. Навигация осуществляется следующим образом: зная индекс родительского элемента (parent) легко можем найти индексы дочерних элементов (левый - 2 * parent + 1; правый - 2 * parent + 2).

Заготовка класса

public class BinaryHeap
{
    private List<int> heap_list = new List<int>();

    public int heapSize
    {
        get
        {
            return this.heap_list.Count;
        }
    }
}

Просеивание элемента вниз

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

Метод Heapify необходим нам для написания метода, строящего пирамиду.

public void Heapify(int i, int last) //просеивание вниз 
{
    int parent = i;

    while (true)
    {
        int left_child = 2 * parent + 1;
        int right_child = 2 * parent + 2;
        int max_child = parent;

        if (left_child <= last && 
        heap_list[parent] < heap_list[left_child])
        {
            max_child = left_child;
        }

        if (right_child <= last && 
        heap_list[left_child] < heap_list[right_child] && 
        heap_list[right_child] > heap_list[parent])
        {
            max_child = right_child;
        } 

        if (parent == max_child) break;

        int temp = heap_list[parent];
        heap_list[parent] = heap_list[max_child];
        heap_list[max_child] = temp;

        parent = max_child;
    }
}

Построение пирамиды

1. Записываем входной массив в массив будущей пирамиды (heap_list и Source теперь ссылки на один массив).
2. Просеиваем вниз все элементы, начиная с середины.

public void Build_Heap(List<int> Source)
{
    heap_list = Source;


    for (int i = heapSize >> 1; i >= 0; i--)
    {
        Heapify(i, heapSize-1); //просеивание по элементам от i до heapSize-1
    }

}

Сортировка

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

public void Heap_Sort(List<int> Source)
{
    Build_Heap(Source);

    for (int i = Source.Count - 1; i >= 0; i--)
    {
        int temp = heap_list[i];
        heap_list[i] = heap_list[0];
        heap_list[0] = temp;
        Heapify(0, i - 1);
    }
}

Характеристики алгоритма