Алгоритмы сортировки. HeapSort

Dimka Maleev
3 min readApr 9, 2015

--

Ну вот и дошли до алгоритма, в котором начинаем говорить о структурах даных. HeapSort это усовершенствованный SelectionSort, но работающей с кучей ( heap ). Этот алгоритм немного медленее чем QuickSort, на даже в самом худшем случае имеет сложность O(nlogn), в отличии от того же QuickSort который деградирует аж до O(n^2).

Итак, что такое куча? Heap — это деревообразная структура, в которой выполняется одно правило: если элемент B потомок элемента А, то значение A > B.

Одной из реализаций heap— может быть binary heap( двоичная куча ) , в котором выполняется такие условия:

  1. Значение отцов больше чем значение потомков ( max-heap, существует еще min-heap где все наоборот☺ )
  2. Глубина листьев отличается не больше чем на 1 слой
  3. Последний слой заполняется с лево на право.

Удобной структурой для хранения сортирующей кучи ( так еще называют binary heap ) — является массив, у которого первый элемент a[0] — корень дерева ( то есть самый большой элемент ) .

Для начала, давайте построим саму структуру даных. То что я встречал в практике, делиться на 2 типа:

  1. Построение структуры с ее методами, и тому подобное ( ООП языки, Сейджвик, все дела)
  2. Простое использование массива, с дополнительными методами

ООП реализацию кучи мы обязательно обсудим в следующем посту, потому сегодня просто используем метод 2.

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

/**
* deeps down to the children, and check if children is less then parent
*/
function sink(array, i, max){
var big_index, child;
while( i < max ) {
big_index = i;
childl = 2 * i + 1;
childr = childl + 1;
if (childl < max && array[childl] > array[big_index])
big_index = childl;

if (childr < max && array[childr] > array[big_index])
big_index = childr;

if (big_index == i) return;
array.swap(i, big_index);
i = big_index;
}
}
/**
* build heap from the array
*/
function build_heap(array){
var index = Math.floor((array.length / 2) — 1) ;
while ( index >= 0 ){
sink(array, index, array.length);
index —- ;
}
}

Как видим, у нас есть функция build_heap которая начиная с половины массива, вызывает функцию sink. Функция sink бегает по всем детям листа который мы указали и проверяет или они действительно меньше, если нет — меняем элементы местами. После того как пробежались по всем детям, и детям его детей, и … мы возвращаемся, и начинаем проверять у элемента перед проверенным, и так да самого первого элемента. В результате мы получаем бинарную кучу, с самым большим элементом находящемся на первом месте.

С половины мы начинаем, чтоб точно проверить все элементы☺

Сам код сортировки невероятно простой:

 /**
* start soring
*/
function heapSort(array){
build_heap(array);
var end = array.length — 1;

while(end >= 0) {
array.swap(0, end);
sink(array, 0, end);
end -= 1
}
return array;
}

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

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

К сожалению, венгерского танца heapsort я не нашел, потому вам немного модерна:

Итак, результаты:

Исходники примеров вы можете найти тут.

--

--

Dimka Maleev

Software Engineer @ Denizen