Алгоритмы сортировки. HeapSort
--
Ну вот и дошли до алгоритма, в котором начинаем говорить о структурах даных. HeapSort это усовершенствованный SelectionSort, но работающей с кучей ( heap ). Этот алгоритм немного медленее чем QuickSort, на даже в самом худшем случае имеет сложность O(nlogn), в отличии от того же QuickSort который деградирует аж до O(n^2).
Итак, что такое куча? Heap — это деревообразная структура, в которой выполняется одно правило: если элемент B потомок элемента А, то значение A > B.
Одной из реализаций heap— может быть binary heap( двоичная куча ) , в котором выполняется такие условия:
- Значение отцов больше чем значение потомков ( max-heap, существует еще min-heap где все наоборот☺ )
- Глубина листьев отличается не больше чем на 1 слой
- Последний слой заполняется с лево на право.
Удобной структурой для хранения сортирующей кучи ( так еще называют binary heap ) — является массив, у которого первый элемент a[0] — корень дерева ( то есть самый большой элемент ) .
Для начала, давайте построим саму структуру даных. То что я встречал в практике, делиться на 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 я не нашел, потому вам немного модерна:
Итак, результаты:
Исходники примеров вы можете найти тут.