Оптимизация сортировки кучей
В пирамидальной сортировке из предыдущего раздела мы выделяли дополнительное пространство для построения кучи и её сортировки. В этом разделе мы оптимизируем это, используя пирамидальную сортировку на месте.
Для максимальной кучи сначала поменяйте местами данные в начальной позиции со значением в конце массива, так что конец массива становится максимальным элементом. Затем выполните операцию просеивания вниз для элемента W, чтобы восстановить максимальную кучу. Далее поменяйте местами вновь полученное максимальное значение с предпоследней позицией всего массива, чтобы предпоследняя позиция содержала второе по величине значение. Этот процесс продолжается по аналогии.
Весь процесс можно проиллюстрировать следующей диаграммой:

Пример кода на Java
Загрузка пакета исходного кода:Скачать
Код файла src/example/heap/HeapSort.java:
import example.sort.SortTestHelper;
/**
* Пирамидальная сортировка на месте
*/
public class HeapSort<T extends Comparable> {
public static void sort(Comparable[] arr) {
int n = arr.length;
// Обратите внимание, что на данном этапе наша куча индексируется начиная с 0
// Начинаем с (индекса последнего элемента - 1) / 2
// Индекс последнего элемента равен n-1
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
shiftDown(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
shiftDown(arr, i, 0);
}
}
// Поменять местами два элемента с индексами i и j в куче
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// Исходный процесс shiftDown
private static void shiftDown(Comparable[] arr, int n, int k) {
while (2 * k + 1 < n) {
// Левый дочерний узел
int j = 2 * k + 1;
// Правый дочерний узел больше левого дочернего узла
if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0)
j += 1;
// Больше обоих дочерних узлов
if (arr[k].compareTo(arr[j]) >= 0) break;
// Поменять местами значения исходного узла и дочернего узла
swap(arr, k, j);
k = j;
}
}
// Тест HeapSort
public static void main(String[] args) {
int N = 100;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
sort(arr);
// Постепенно извлекайте данные в heapify с помощью extractMax
// Порядок извлечения должен быть от наибольшего к наименьшему
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
// Убедитесь, что массив arr отсортирован от наибольшего к наименьшему
for (int i = 1; i < N; i++)
assert arr[i - 1] >= arr[i];
}
}