bm1120836 / algorithms_hw2 Goto Github PK

Метод main() класса HeapSortApp:

1. запрашивает у пользователя размер массива;
2. заполняет массив случайными данными;
3. преобразует массив в пирамиду N/2 с применениями метода trickleDown();
4. извлекает элементы из кучи и записывает их обратно в конец массива.

После каждого шага выводится содержимое массива.
Пример вывода программы heapSort.java:
Enter number of items: 10
Random: 81 6 23 38 95 71 72 39 34 53
Heap: 95 81 72 39 53 71 23 38 34 6

Пирамидальная сортировка выполняется за время
O(N в степени logN). Хотя по скорости она слегка уступает быстрой сортировке,
ее преимуществом перед быстрой сортировкой является меньшая чувствительность
к исходному распределению данных. При некоторых конфигурациях ключей
быстрая сортировка замедляется до O(N2),
тогда как пирамидальная сортировка
выполняется за время O(N в степени logN) независимо от распределения данных.