Что такое пирамидальная сортировка

1️⃣ Как кратко ответить

Пирамидальная сортировка (или Heap Sort) — это алгоритм сортировки, который использует структуру данных "куча" для упорядочивания элементов. Он работает в два основных этапа: сначала строит максимальную кучу из массива, затем последовательно извлекает максимальный элемент из кучи и перестраивает её, обеспечивая упорядоченность. Алгоритм имеет временную сложность O(n log n) и не требует дополнительной памяти, так как сортировка выполняется на месте.

2️⃣ Подробное объяснение темы

Пирамидальная сортировка — это алгоритм, который использует структуру данных "куча" (heap) для сортировки массива. Куча — это двоичное дерево, которое удовлетворяет свойству кучи: для максимальной кучи каждый родительский узел больше или равен своим дочерним узлам. Это свойство позволяет быстро находить максимальный элемент.

Основные этапы пирамидальной сортировки:

1. Построение кучи: Преобразование исходного массива в максимальную кучу.
2. Сортировка: Повторное извлечение максимального элемента из кучи и перестроение кучи.

Пример кода на C++:

#include <iostream>
#include <vector>
​
// Функция для перестройки поддерева с корнем в узле i, размер кучи n
void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i; // Инициализируем наибольший элемент как корень
    int left = 2 * i + 1; // Левый дочерний элемент
    int right = 2 * i + 2; // Правый дочерний элемент
​
    // Если левый дочерний элемент больше корня
    if (left < n && arr[left] > arr[largest])
        largest = left;
​
    // Если правый дочерний элемент больше, чем самый большой элемент на данный момент
    if (right < n && arr[right] > arr[largest])
        largest = right;
​
    // Если самый большой элемент не корень
    if (largest != i) {
        std::swap(arr[i], arr[largest]); // Меняем местами
​
        // Рекурсивно перестраиваем затронутое поддерево
        heapify(arr, n, largest);
    }
}
​
// Основная функция для выполнения пирамидальной сортировки
void heapSort(std::vector<int>& arr) {
    int n = arr.size();
​
    // Построение кучи (перегруппировка массива)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
​
    // Один за другим извлекаем элементы из кучи
    for (int i = n - 1; i > 0; i--) {
        // Перемещаем текущий корень в конец
        std::swap(arr[0], arr[i]);
​
        // Вызываем heapify на уменьшенной куче
        heapify(arr, i, 0);
    }
}
​
int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    heapSort(arr);
​
    std::cout << "Sorted array is \n";
    for (int i : arr)
        std::cout << i << " ";
    return 0;
}

Объяснение кода:

• Функция heapify: Перестраивает поддерево с корнем в узле i так, чтобы оно удовлетворяло свойству кучи. Сначала определяется наибольший элемент среди корня, левого и правого дочерних узлов. Если наибольший элемент не корень, они меняются местами, и процесс повторяется рекурсивно для затронутого поддерева.

• Функция heapSort: Сначала строит максимальную кучу из массива. Затем, начиная с конца массива, последовательно извлекает максимальный элемент (корень кучи) и помещает его в конец массива, уменьшая размер кучи. После каждого извлечения вызывается heapify для восстановления свойства кучи.

Применение и преимущества:

Пирамидальная сортировка используется в ситуациях, когда требуется сортировка на месте с гарантированной временной сложностью O(n log n). Она не требует дополнительной памяти, что делает её подходящей для сортировки больших массивов. Однако, в отличие от некоторых других алгоритмов, таких как Quick Sort, она не является стабильной, то есть не сохраняет порядок равных элементов.