Dyzzet|
C++ Data Science Алгоритмы Темы · Блог · YouTube
Пирамидальная сортировка
Интерактивная анимация
Авторы: Dyzzet, joparino

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

heapsort() сперва вызывает функцию heapify(), которая особым образом перестраивает массив: превращает его в кучу. Изначально элементы массива располагаются так: нулевой элемент — корень, следующие два элемента — потомки корневого узла и т. д.

Поскольку самый большой элемент — корневой, то есть нулевой элемент массива, он обменивается с последним (последний элемент больше не будет перемещаться).

Но свойства кучи оказываются нарушенными, поэтому вызывается функция siftDown() (другие варианты термина sift down: bubble down, push down, fix down), которая эти свойства восстанавливает: «просеивает» элемент с вершины кучи до некоторой позиции так, чтобы в итоге восстановились свойства кучи. В альтернативном варианте элементы просеиваются наверх.

Код использует функцию parentIndex() для вычисления индекса родительского узла в куче по индексу узла \(p(i)=\left\lfloor\dfrac{i - 1}{2}\right\rfloor,\) leftChildIndex() — для вычисления индекса левого потомка: \(l(i)=2i+1,\) rightChildIndex() — для правого: \(r(i)=2i+2.\)

Просеивание вниз

Просеивание наверх

 
function heapsort(data[], count) { heapify(data, count); end = count - 1; while (end > 0) { swap(data[0], data[end]); --end; siftDown(data, 0, end); } }
function heapify(data[], count) { start = parentIndex(count - 1); while (start >= 0) { siftDown(data, start, count - 1); --start; } }
function siftDown(data[], start, end) { root = start; while (leftChildIndex(root) <= end) { child = leftChildIndex(root); temp = root; if (data[temp] < data[child]) { temp = child; } if (child + 1 <= end && data[temp] < data[child + 1]) { temp = child + 1; } if (temp == root) { return; } else { swap(data[root], data[temp]); root = temp; } } }
function heapsort(data[], count) { heapify(data, count); end = count - 1; while (end > 0) { swap(data[0], data[end]); --end; heapify(data, end); } }
function heapify(data[], count) { end = 1; while (end < count) { siftUp(data, 0, end); ++end; } }
function siftUp(data[], start, end) { child = end; while (child > start) { parent = parentIndext(child); if (data[parent] < data[child]) { swap(data[parent], data[child]); child = parent; } else { return; } } }
19 июля 2022
Зарегистрируйтесь и войдите, чтобы оставлять комментарии и голосовать.

Сортировки
Сортировка пузырьком
Сортировка выбором
Гномья сортировка
Сортировка вставками
Сортировка Шелла
Быстрая сортировка
Быстрая сортировка. Вариант с указателем
Пирамидальная сортировка
Также может быть интересным
© MMXI—MMXXIII. RSS. Поддержать сайт
Светлая тема / тёмная тема