Оптимизация сортировки кучей

В пирамидальной сортировке из предыдущего раздела мы выделяли дополнительное пространство для построения кучи и её сортировки. В этом разделе мы оптимизируем это, используя пирамидальную сортировку на месте.

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

Весь процесс можно проиллюстрировать следующей диаграммой:

Пример кода на Java

Загрузка пакета исходного кода:Скачать

Код файла src/example/heap/HeapSort.java:

package example.heap;

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];
    }
}
Другие расширения