company_banner

Пирамидальная сортировка (HeapSort)

Автор оригинала: Shivi Aggarwal
  • Перевод


Перевод статьи подготовлен специально для студентов курса «Алгоритмы для разработчиков».




Пирамидальная сортировка (или сортировка кучей, HeapSort) — это метод сортировки сравнением, основанный на такой структуре данных как двоичная куча. Она похожа на сортировку выбором, где мы сначала ищем максимальный элемент и помещаем его в конец. Далее мы повторяем ту же операцию для оставшихся элементов.


Что такое двоичная куча?


Давайте сначала определим законченное двоичное дерево. Законченное двоичное дерево — это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, имеет полный набор узлов, и все листья расположены как можно левее (Источник Википедия).


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


Почему для двоичной кучи используется представление на основе массива ?


Поскольку двоичная куча — это законченное двоичное дерево, ее можно легко представить в виде массива, а представление на основе массива является эффективным с точки зрения расхода памяти. Если родительский узел хранится в индексе I, левый дочерний элемент может быть вычислен как 2 I + 1, а правый дочерний элемент — как 2 I + 2 (при условии, что индексирование начинается с 0).


Алгоритм пирамидальной сортировки в порядке по возрастанию:


  1. Постройте max-heap из входных данных.
  2. На данном этапе самый большой элемент хранится в корне кучи. Замените его на последний элемент кучи, а затем уменьшите ее размер на 1. Наконец, преобразуйте полученное дерево в max-heap с новым корнем.
  3. Повторяйте вышеуказанные шаги, пока размер кучи больше 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 Kumra

C 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).


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


  1. Отсортировать почти отсортированный (или отсортированный на K позиций) массив ;
  2. k самых больших (или самых маленьких) элементов в массиве.

Алгоритм пирамидальной сортировки имеет ограниченное применение, потому что Quicksort (Быстрая сортировка) и Mergesort (Сортировка слиянием) на практике лучше. Тем не менее, сама структура данных кучи используется довольно часто. См. Применения структуры данных кучи



Скриншоты:

— (Теперь, когда мы построили кучу, мы должны преобразовать ее в max-heap)



— (В max-heap родительский узел всегда больше или равен по отношению к дочерним
10 больше 4. Поэтому мы меняем местами 4 и 10)

— (В max-heap родительский узел всегда больше или равен по отношению к дочерним
5 больше 4. По этому мы меняем местами 5 и 4)



— (Меняем местами первый и последний узлы и удаляем последний из кучи)


Тест по пирамидальной сортировке


Другие алгоритмы сортировки на GeeksforGeeks/GeeksQuiz:
Быстрая сортировка, Сортировка выбором, Сортировка пузырьком, Сортировка вставками, Сортировка слиянием, Пирамидальная сортировка, Поразрядная сортировка, Сортировка подсчетом, Блочная сортировка, Сортировка Шелла, Сортировка расческой, Сортировка подсчетом со списком.


Практикум по сортировке


Пожалуйста, оставляйте комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

  • +26
  • 6,6k
  • 6
OTUS. Онлайн-образование
558,90
Цифровые навыки от ведущих экспертов
Поделиться публикацией

Комментарии 6

    +3

    Изящный алгоритм с хорошими гарантиями производительности, когда изучил впервые, был очень впечатлён.

      0
      Полезная статья! Очень полезная! Очень очень полезная! Но как по мне слишком большой порог вхождения, можно сначала пузырьковую сортировку на всех языках мира?
        +2
        Тема сортировок очень интересна!
        +1
        Спасибо, нам нужно больше копипасты с гитхаба.
          0
          Я понимаю, что это всего лишь перевод статьи с geeksforgeeks (образовательные статьи с geeksforgeeks?) по очень избитой теме, но перевести ведь можно и получше, есть ведь какая-то общепринятая терминология в русском языке.

          1. «Законченное двоичное дерево».
          Возможно, этот термин где-нибудь и применяется, но обычно это либо называют «полным двоичным деревом», либо вообще никак не называют, описывая правила построения

          2. «Пирамидальная сортировка — это вполне годный алгоритм. Его типичная реализация не стабильна, но может быть таковой сделана».
          Не стабильна, близка к распаду. Вроде бы обычно в русском языке термин «stable sort» называют «устойчивой сортировкой».

          3. Описание алгоритма.
          «Наконец, преобразуйте полученное дерево в max-heap с новым корнем.».
          В оригинале ведь все куда более конкретно: «Finally, heapify the root of tree.» и затем идет описание того, что же такое «heapify». В переводе термин «heapify» потерян, из-за этого логика становится куда более размытой.
          Также третий пункт описания алгоритма «Повторяйте вышеуказанные шаги, пока размер кучи больше 1.» в оригинале написан неудачно (не очень понятно. нужно повторять шаги 1 и 2 или только 2), и тут также оставлен без изменений (причем русскоязычный вариант субъективно еще менее понятный).
          В результате по описанию этого простого алгоритма, на мой взгляд, вообще мало что понятно без чтения кода или дополнительного поиска информации (что возвращает нас к теме качества статей на geeksforgeeks).
            +1
            Его типичная реализация не стабильна, но может быть таковой сделана (см. Здесь).

            Так себе решение. Для достижения стабильности потребуется O(n) памяти и еще больше просадит производительность. Скорее всего получится хуже по всем параметрам, чем merge sort.
            Идеального алгоритмя до сих пор нет (гарантированая сложность O(n * log n), константа (или хотя бы логарифм) по памяти, стабильность).

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое