Вступление
Heapsort — это один из общих алгоритмов сортировки, который работает в O (n.log (n)) в худшем случае, точно так же, как сортировка слиянием и быстрая сортировка , но сортирует на месте — как быстрая сортировка. Хотя время сортировки в худшем случае для быстрой сортировки равно O (n 2 ), часто считается, что на практике оно превосходит другие алгоритмы сортировки. Таким образом, на практике быстрая сортировка «быстрее», чем heapsort. В то же время разработчики склонны считать, что heapsort сложнее реализовать, чем другие алгоритмы сортировки n.log (n).
С другой стороны, для сортировки элементов в heapsort используется специальная структура данных, называемая кучей, и в некоторых конкретных случаях эта структура данных весьма полезна. Таким образом, чтобы понять, что такое куча, сначала нужно понять, что такое куча.
Итак, сначала давайте посмотрим, что такое куча.
обзор
Куча — это полное двоичное дерево, где все родители больше своих детей (максимальная куча). Если все дети больше, чем их родители, считается, что куча — это минимальная куча. Но сначала, что такое полное двоичное дерево? Ну, это бинарное дерево, где все уровни заполнены, кроме последнего, где все элементы расположены слева (как на рисунке ниже).
Полное двоичное дерево — это структура, в которой все уровни полностью заполнены, кроме последнего уровня, где все элементы размещены слева!
В сочетании с тем фактом, что каждый узел содержит больший ключ, чем его дочерние элементы, куча может выглядеть как дерево на следующей диаграмме.
В max-heap каждый узел содержит большее значение, чем его дочерние элементы. Соответственно в минимальной куче каждый узел содержит меньшее значение, чем его родительский элемент!
Дело в том, что если мы поместим индексы рядом с каждым узлом этого дерева, начиная с корня (индекс 1) и продолжая слева направо на каждом уровне, мы получим следующее дерево.
Размещение индексов прямо на каждом узле раскрывает секрет кучи. У i-го узла точно есть дочерний элемент с индексом 2 * i, а правый дочерний элемент с индексом 2 * i + 1! Это прекрасная возможность поместить это дерево в массив!
Теперь, если мы более внимательно посмотрим на рисунок выше, мы увидим, что индексы узла и его дочерних элементов тесно связаны. Таким образом, для узла индекса i мы видим, что его левый потомок имеет индекс 2 * i , тогда как индекс его правого потомка равен 2 * i + 1 .
Этот конкретный порядок дает нам возможность хранить каждую кучу в массиве.
Дерево кучи может быть легко представлено в виде массива!
Поскольку в куче его больший элемент находится в корне дерева (для max-heap, соответственно, в минимальной куче его наименьший элемент — корень), нам нужно ответить на два вопроса.
- Как построить кучу из обычного массива?
- После извлечения корня, который является самым большим (самым маленьким) элементом, как мы можем восстановить кучу, чтобы снова сохранить ее?
Сначала попробуем ответить на первый вопрос. Как построить кучу? Что ж, давайте ненадолго забудем о массиве и посмотрим на обычное двоичное дерево только с тремя узлами.
Исправление узла и его дочерних элементов для формирования правильной кучи часто называется heapify!
Мы видим, что три зеленых узла разрушают структуру нашей кучи, потому что корень (1) меньше, чем его дочерние элементы (4) и (5). Таким образом, мы должны решить эту проблему, и мы собираемся поменять корень с его самым большим потомком.
Сначала нам нужно узнать, какой из трех элементов является наибольшим, а затем, если это не корень, поменять его значение на корень!
Как вы можете видеть на картинке выше, i-й элемент сначала сравнивается с его левым потомком. Большой из этих двух предметов сравнивается с правильным ребенком. Обратите внимание, что мы не меняем их местами — мы просто сравниваем их, чтобы определить, какой из них больше. Как только мы находим наибольшее из этих трех значений, мы меняем их корнем на случай, если это не корневое значение.
Хотя теперь эти три элемента образуют кучу, замена корня одним из его дочерних элементов может уничтожить кучу, созданную из этого дочернего элемента. Вот почему мы продолжаем ту же процедуру с ним.
Это фактически дает нам процедуру для кучи трех узлов, созданных из i-го элемента и его дочерних элементов. Однако, чтобы построить кучу из произвольного массива, мы должны выполнить эту операцию, начиная с пола (len [A] / 2) и заканчивая первым элементом в массиве.
Построение случайного массива в кучу не так сложно, так как мы знаем, что половина всех элементов дерева лежит на самом низком уровне! Таким образом, мы начинаем с пола (len [A] / 2)!
Зачем? Ну, полное двоичное дерево с полным последним уровнем содержит n / 2 + 1 узлов в нем. У них нет детей, поэтому нам не нужно их проверять — они «отсортированы». Действительно, если мы начнем с элемента справа от пола (len [A] / 2), не будет элементов с индексами 2 * i и 2 * i + 1 .
Код
Пока мы знаем, как построить кучу. Далее нужно поменять местами первый и последний элемент массива и перестроить кучу. Вот код PHP, как это сделать.
$a = array(1, 6, 3, 8, 2, 5, 4);
function heapify(&$a, &$i, &$heap_size)
{
$l = $i*2 + 1;
$r = $i*2 + 2;
if ($l < $heap_size && $a[$i] < $a[$l]) {
$largest = $l;
} else {
$largest = $i;
}
if ($r < $heap_size && $a[$largest] < $a[$r]) {
$largest = $r;
}
if ($largest != $i) {
$t = $a[$i];
$a[$i] = $a[$largest];
$a[$largest] = $t;
heapify($a, $largest, $heap_size);
}
}
function build_heap(&$a, &$heap_size)
{
$len = floor($heap_size / 2);
for ($i = $len; $i > -1; $i--) {
heapify($a, $i, $heap_size);
}
}
function heapsort(&$a)
{
$heap_size = count($a);
build_heap($a, $heap_size);
while ($heap_size--) {
$t = $a[$heap_size];
$a[$heap_size] = $a[0];
$a[0] = $t;
build_heap($a, $heap_size);
}
}
// 1 2 3 4 5 6 8
heapsort($a);
сложность
Хорошо, последний вопрос — как мы узнаем, что этот алгоритм сортируется за время n.log (n)? Давайте рассмотрим алгоритм еще раз. Наихудший случай heapify — это когда мы начинаем с корня до самого низкого уровня дерева. В этих условиях, если высота дерева равна h , время равно O (h), а поскольку дерево сбалансировано (завершено), время в терминах n равно O (log (n)).
In the other hand to build a heap we walk from floor(len[A] / 2) to 0, which makes it run in O(n.log(n)). However there is only one case when the heapify may run in log(n), and that is when it starts from the root, so it’s not absolutely true that building the heap runs in n.log(n).
Indeed heapify depend on the level it has been started. It doesn’t run for the last ceil(n/2) items and it runs in O(1) for another 2h-1. Thus in practice we can build a heap in O(n).
Once we have the heap built, the only thing to do is to extract its first element and rebuild – heapify from the first item. This makes the sorting algorithm run in O(n.log(n)) – just like quicksort and mergesort.
Application
As I said in the beginning of this post quicksort is often the fastest general purpose algorithm in practice. This makes both merge sort and heapsort not so popular. However heapsort introduces an interesting data structure which can help us in many other cases.
It’s initially used to implement priority queues. What is great about a heap is that after we build it, which we know how to do in linear time, we can extract the greatest value – thus taking the highest priority task. Then with rebuilding the heap we can extract the next priority and so on, without fully sorting the array.
This makes the heapsort the only sorting algorithm that can sort the first k items out of a set of n items without sorting the whole set.
Indeed let’s say we have a set of positive integers and we’d like to get the biggest sum out of three items. Obviously we can sort the array and take the greatest three numbers, but this will cost us n.log(n) time, while using heapsort we can do it much faster! And all this without extra space – in place!