Перевод статьи подготовлен специально для студентов курса «Алгоритмы для разработчиков».
Пирамидальная сортировка (или сортировка кучей, HeapSort) — это метод сортировки сравнением, основанный на такой структуре данных как двоичная куча. Она похожа на сортировку выбором, где мы сначала ищем максимальный элемент и помещаем его в конец. Далее мы повторяем ту же операцию для оставшихся элементов.
Что такое двоичная куча?
Давайте сначала определим законченное двоичное дерево. Законченное двоичное дерево — это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, имеет полный набор узлов, и все листья расположены как можно левее (Источник Википедия).
Двоичная куча — это законченное двоичное дерево, в котором элементы хранятся в особом порядке: значение в родительском узле больше (или меньше) значений в его двух дочерних узлах. Первый вариант называется max-heap, а второй — min-heap. Куча может быть представлена двоичным деревом или массивом.
Почему для двоичной кучи используется представление на основе массива ?
Поскольку двоичная куча — это законченное двоичное дерево, ее можно легко представить в виде массива, а представление на основе массива является эффективным с точки зрения расхода памяти. Если родительский узел хранится в индексе I, левый дочерний элемент может быть вычислен как 2 I + 1, а правый дочерний элемент — как 2 I + 2 (при условии, что индексирование начинается с 0).
Алгоритм пирамидальной сортировки в порядке по возрастанию:
- Постройте max-heap из входных данных.
- На данном этапе самый большой элемент хранится в корне кучи. Замените его на последний элемент кучи, а затем уменьшите ее размер на 1. Наконец, преобразуйте полученное дерево в max-heap с новым корнем.
- Повторяйте вышеуказанные шаги, пока размер кучи больше 1.
Как построить кучу?
Процедура преобразования в кучу (далее процедура heapify) может быть применена к узлу, только если его дочерние узлы уже преобразованы. Таким образом, преобразование должно выполняться снизу вверх. Давайте разберемся с помощью примера:
Входные данные: 4, 10, 3, 5, 1
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
Числа в скобках представляют индексы в представлении данных в виде массива.
Применение процедуры heapify к индексу 1:
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
Применение процедуры heapify к индексу 0:
10(0)
/ \
5(1) 3(2)
/ \
4(3) 1(4)
Процедура heapify вызывает себя рекурсивно для создания кучи сверху вниз.Рекомендация: Пожалуйста, сначала решите задачу на “PRACTICE”, прежде чем переходить к решению.
C++
// Реализация пирамидальной сортировки на C++
#include <iostream>
using namespace std;
// Процедура для преобразования в двоичную кучу поддерева с корневым узлом i, что является
// индексом в arr[]. n - размер кучи
void heapify(int arr[], int n, int i)
{
int largest = i;
// Инициализируем наибольший элемент как корень
int l = 2*i + 1; // левый = 2*i + 1
int r = 2*i + 2; // правый = 2*i + 2
// Если левый дочерний элемент больше корня
if (l < n && arr[l] > arr[largest])
largest = l;
// Если правый дочерний элемент больше, чем самый большой элемент на данный момент
if (r < n && arr[r] > arr[largest])
largest = r;
// Если самый большой элемент не корень
if (largest != i)
{
swap(arr[i], arr[largest]);
// Рекурсивно преобразуем в двоичную кучу затронутое поддерево
heapify(arr, n, largest);
}
}
// Основная функция, выполняющая пирамидальную сортировку
void heapSort(int arr[], int n)
{
// Построение кучи (перегруппируем массив)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Один за другим извлекаем элементы из кучи
for (int i=n-1; i>=0; i--)
{
// Перемещаем текущий корень в конец
swap(arr[0], arr[i]);
// вызываем процедуру heapify на уменьшенной куче
heapify(arr, i, 0);
}
}
/* Вспомогательная функция для вывода на экран массива размера n*/
void printArray(int arr[], int n)
{
for (int i=0; i<n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Управляющая программа
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
}Java
// Реализация пирамидальной сортировки на Java
public class HeapSort
{
public void sort(int arr[])
{
int n = arr.length;
// Построение кучи (перегруппируем массив)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Один за другим извлекаем элементы из кучи
for (int i=n-1; i>=0; i--)
{
// Перемещаем текущий корень в конец
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Вызываем процедуру heapify на уменьшенной куче
heapify(arr, i, 0);
}
}
// Процедура для преобразования в двоичную кучу поддерева с корневым узлом i, что является
// индексом в arr[]. n - размер кучи
void heapify(int arr[], int n, int i)
{
int largest = i; // Инициализируем наибольший элемент как корень
int l = 2*i + 1; // левый = 2*i + 1
int r = 2*i + 2; // правый = 2*i + 2
// Если левый дочерний элемент больше корня
if (l < n && arr[l] > arr[largest])
largest = l;
// Если правый дочерний элемент больше, чем самый большой элемент на данный момент
if (r < n && arr[r] > arr[largest])
largest = r;
// Если самый большой элемент не корень
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Рекурсивно преобразуем в двоичную кучу затронутое поддерево
heapify(arr, n, largest);
}
}
/* Вспомогательная функция для вывода на экран массива размера n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Управляющая программа
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}Python
# Реализация пирамидальной сортировки на Python
# Процедура для преобразования в двоичную кучу поддерева с корневым узлом i, что является индексом в arr[]. n - размер кучи
def heapify(arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
# Проверяем существует ли левый дочерний элемент больший, чем корень
if l < n and arr[i] < arr[l]:
largest = l
# Проверяем существует ли правый дочерний элемент больший, чем корень
if r < n and arr[largest] < arr[r]:
largest = r
# Заменяем корень, если нужно
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # свап
# Применяем heapify к корню.
heapify(arr, n, largest)
# Основная функция для сортировки массива заданного размера
def heapSort(arr):
n = len(arr)
# Построение max-heap.
for i in range(n, -1, -1):
heapify(arr, n, i)
# Один за другим извлекаем элементы
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # свап
heapify(arr, i, 0)
# Управляющий код для тестирования
arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
print ("%d" %arr[i]),
# Этот код предоставил Mohit KumraC Sharp
// Реализация пирамидальной сортировки на C#
using System;
public class HeapSort
{
public void sort(int[] arr)
{
int n = arr.Length;
// Построение кучи (перегруппируем массив)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Один за другим извлекаем элементы из кучи
for (int i=n-1; i>=0; i--)
{
// Перемещаем текущий корень в конец
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// вызываем процедуру heapify на уменьшенной куче
heapify(arr, i, 0);
}
}
// Процедура для преобразования в двоичную кучу поддерева с корневым узлом i, что является
// индексом в arr[]. n - размер кучи
void heapify(int[] arr, int n, int i)
{
int largest = i;
// Инициализируем наибольший элемент как корень
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// Если левый дочерний элемент больше корня
if (l < n && arr[l] > arr[largest])
largest = l;
// Если правый дочерний элемент больше, чем самый большой элемент на данный момент
if (r < n && arr[r] > arr[largest])
largest = r;
// Если самый большой элемент не корень
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Рекурсивно преобразуем в двоичную кучу затронутое поддерево
heapify(arr, n, largest);
}
}
/* Вспомогательная функция для вывода на экран массива размера n */
static void printArray(int[] arr)
{
int n = arr.Length;
for (int i=0; i<n; ++i)
Console.Write(arr[i]+" ");
Console.Read();
}
//Управляющая программа
public static void Main()
{
int[] arr = {12, 11, 13, 5, 6, 7};
int n = arr.Length;
HeapSort ob = new HeapSort();
ob.sort(arr);
Console.WriteLine("Sorted array is");
printArray(arr);
}
}
//Этот код предоставил
// Akanksha Ra (Abby_akku)PHP
<?php
// Реализация пирамидальной сортировки на Php
// Процедура для преобразования в двоичную кучу поддерева с корневым узлом i, что является
// индексом в arr[]. n - размер кучи
function heapify(&$arr, $n, $i)
{
$largest = $i; // Инициализируем наибольший элемент как корень
$l = 2*$i + 1; // левый = 2*i + 1
$r = 2*$i + 2; // правый = 2*i + 2
// Если левый дочерний элемент больше корня
if ($l < $n && $arr[$l] > $arr[$largest])
$largest = $l;
//Если правый дочерний элемент больше, чем самый большой элемент на данный момент
if ($r < $n && $arr[$r] > $arr[$largest])
$largest = $r;
// Если самый большой элемент не корень
if ($largest != $i)
{
$swap = $arr[$i];
$arr[$i] = $arr[$largest];
$arr[$largest] = $swap;
// Рекурсивно преобразуем в двоичную кучу затронутое поддерево
heapify($arr, $n, $largest);
}
}
//Основная функция, выполняющая пирамидальную сортировку
function heapSort(&$arr, $n)
{
// Построение кучи (перегруппируем массив)
for ($i = $n / 2 - 1; $i >= 0; $i--)
heapify($arr, $n, $i);
//Один за другим извлекаем элементы из кучи
for ($i = $n-1; $i >= 0; $i--)
{
// Перемещаем текущий корень в конец
$temp = $arr[0];
$arr[0] = $arr[$i];
$arr[$i] = $temp;
// вызываем процедуру heapify на уменьшенной куче
heapify($arr, $i, 0);
}
}
/* Вспомогательная функция для вывода на экран массива размера n */
function printArray(&$arr, $n)
{
for ($i = 0; $i < $n; ++$i)
echo ($arr[$i]." ") ;
}
// Управляющая программа
$arr = array(12, 11, 13, 5, 6, 7);
$n = sizeof($arr)/sizeof($arr[0]);
heapSort($arr, $n);
echo 'Sorted array is ' . "\n";
printArray($arr , $n);
// Этот код предоставил Shivi_Aggarwal
?>Вывод:
Отсортированный массив:
5 6 7 11 12 13Здесь предыдущий C-код для справки.
Замечания:
Пирамидальная сортировка — это вполне годный алгоритм. Его типичная реализация не стабильна, но может быть таковой сделана (см. Здесь).
Временная сложность: Временная сложность heapify — O(Logn). Временная сложность createAndBuildHeap() равна O(n), а общее время работы пирамидальной сортировки — O(nLogn).
Применения пирамидальной сортировки:
- Отсортировать почти отсортированный (или отсортированный на K позиций) массив ;
- k самых больших (или самых маленьких) элементов в массиве.
Алгоритм пирамидальной сортировки имеет ограниченное применение, потому что Quicksort (Быстрая сортировка) и Mergesort (Сортировка слиянием) на практике лучше. Тем не менее, сама структура данных кучи используется довольно часто. См. Применения структуры данных кучи
Скриншоты:
— (Теперь, когда мы построили кучу, мы должны преобразовать ее в max-heap)
— (В max-heap родительский узел всегда больше или равен по отношению к дочерним
10 больше 4. Поэтому мы меняем местами 4 и 10)
— (В max-heap родительский узел всегда больше или равен по отношению к дочерним
5 больше 4. По этому мы меняем местами 5 и 4)
— (Меняем местами первый и последний узлы и удаляем последний из кучи)
Тест по пирамидальной сортировке
Другие алгоритмы сортировки на GeeksforGeeks/GeeksQuiz:
Быстрая сортировка, Сортировка выбором, Сортировка пузырьком, Сортировка вставками, Сортировка слиянием, Пирамидальная сортировка, Поразрядная сортировка, Сортировка подсчетом, Блочная сортировка, Сортировка Шелла, Сортировка расческой, Сортировка подсчетом со списком.
Пожалуйста, оставляйте комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
