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

Ну вот и дошли до алгоритма, в котором начинаем говорить о структурах даных. 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 я не нашел, потому вам немного модерна:

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

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