Базовая сортировка кучей
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:
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];
}
}