Метод main() класса HeapSortApp:
- запрашивает у пользователя размер массива;
- заполняет массив случайными данными;
- преобразует массив в пирамиду N/2 с применениями метода trickleDown();
- извлекает элементы из кучи и записывает их обратно в конец массива.
После каждого шага выводится содержимое массива.
Пример вывода программы 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) независимо от распределения данных.