Базовая сортировка кучей

1. Понятие и введение

Пирамидальная сортировка — это алгоритм сортировки, разработанный с использованием структуры данных «куча».

Куча — это структура, которая представляет собой почти полное двоичное дерево и одновременно удовлетворяет свойству кучи: то есть ключ или индекс дочернего узла всегда меньше (или больше) его родительского узла.

II. Инструкция по применению

Наш предыдущий процесс построения кучи заключался во вставке данных по одному в кучу путём вызова метода insert с использованием shift up; временная сложность этого алгоритма равнаO(nlogn), процесс построения пирамидальной сортировки, представленный в этом разделе, называетсяHeapify, временная сложность алгоритма составляетO(n)。

III. Схема процесса

Полное бинарное дерево обладает важным свойством: индекс первого нелистового узла равенn/2значению индекса, полученному взятием целой части, гдеn— количество элементов (при условии, что индексы массива начинаются с 1).

Позиция с индексом 5 — это первый нелистовой узел. Начиная с него, мы двигаемся вперёд по одному, выполняя операцию просеивания вниз для каждого элемента как корневого узла, чтобы соблюсти свойство максимальной кучи.

После операции просеивания вниз для индекса 5 элементы 22 и 62 меняются местами.

Выполните операцию просеивания вниз для элемента с индексом 4.

Выполните операцию просеивания вниз для элемента с индексом 3.

Выполните операцию просеивания вниз для элемента с индексом 2.

Наконец, выполните операцию просеивания вниз для корневого узла, и весь процесс пирамидальной сортировки завершён.

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

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

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

package example.heap;

import example.sort.SortTestHelper;

/**
* Используйте heapify для выполнения пирамидальной сортировки
 */

public class Heapify<T extends Comparable> {

    protected T[] data;
    protected int count;
    protected int capacity;

    // Конструктор, создаёт максимальную кучу из заданного массива
    // Процесс построения кучи имеет временную сложность O(n)
    public Heapify(T arr[]){

        int n = arr.length;

        data = (T[])new Comparable[n+1];
        capacity = n;

        for( int i = 0 ; i < n ; i ++ )
            data[i+1] = arr[i];
        count = n;
        // Начните с первого элемента, который не является листовым узлом
        for( int i = count/2 ; i >= 1 ; i -- )
            shiftDown(i);
    }
    // Вернуть количество элементов в куче
    public int size(){
        return count;
    }
    // Вернуть boolean, указывающий, пуста ли куча
    public boolean isEmpty(){
        return count == 0;
    }
    // Вставить новый элемент item в максимальную кучу
    public void insert(T item){
        assert count + 1 <= capacity;
        data[count+1] = item;
        count ++;
        shiftUp(count);
    }
    // Извлечь верхний элемент из максимальной кучи, т.е. наибольшие данные, хранящиеся в куче
    public T extractMax(){
        assert count > 0;
        T ret = data[1];
        swap( 1 , count );
        count --;
        shiftDown(1);
        return ret;
    }
    // Получить верхний элемент max-кучи
    public T getMax(){
        assert( count > 0 );
        return data[1];
    }


    // Поменять местами два элемента с индексами i и j в куче
    private void swap(int i, int j){
        T t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    //********************
    //* Основные вспомогательные функции max-кучи
    //********************
    private void shiftUp(int k){

        while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){
            swap(k, k/2);
            k /= 2;
        }
    }

    private void shiftDown(int k){

        while( 2*k <= count ){
            int j = 2*k; // В этой итерации цикла data[k] и data[j] меняются местами
            if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
                j ++;
            // data[j] — максимум из data[2*k] и data[2*k+1]

            if( data[k].compareTo(data[j]) >= 0 ) break;
            swap(k, j);
            k = j;
        }
    }

    // Проверка heapify
    public static void main(String[] args) {
        int N = 100;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        Heapify<Integer> heapify = new Heapify<Integer>(arr);
        // Постепенно извлекайте данные в heapify с помощью extractMax
        // Порядок извлечения должен быть от наибольшего к наименьшему
        for( int i = 0 ; i < N ; i ++ ){
            arr[i] = heapify.extractMax();
            System.out.print(arr[i] + " ");
        }

        // Убедитесь, что массив arr отсортирован от наибольшего к наименьшему
        for( int i = 1 ; i < N ; i ++ )
            assert arr[i-1] >= arr[i];
    }
}
Другие расширения