Алгоритм сортировки кучей

Heap Sort, сортировка, алгоритмы

Сортировка кучей - популярный и эффективный алгоритм сортировки в компьютерном программировании. Чтобы научиться писать алгоритм сортировки кучей, требуется знание двух типов структур данных - массивов и деревьев.

Например, начальный набор чисел, которые мы хотим отсортировать, хранится в массиве [10, 3, 76, 34, 23, 32], и после сортировки мы получаем отсортированный массив [3,10,23,32,34,76].

Сортировка кучей работает путем визуализации элементов массива как особого вида полного двоичного дерева, называемого кучей.

Что такое бинарное дерево? Какие виды бинарных деревьев существуют?

Бинарное дерево - это структура данных дерева, в которой каждый родительский узел может иметь не более двух дочерних элементов.

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

Идеальное бинарное дерево похоже на полное бинарное дерево, но с двумя основными отличиями:

1. Каждый уровень должен быть полностью заполнен.
2. Все элементы листа должны наклоняться влево.

Примечание: Последний элемент может не иметь правильного брата, то есть идеальное бинарное дерево не обязательно должно быть полным бинарным деревом.

Как создать полное бинарное дерево из несортированного списка (массива)?

• Выберите первый элемент списка, чтобы он быть корневым узлом. (Первый уровень - 1 элемент).
• Поместите второй элемент в качестве левого дочернего элемента корневого узла, а третий элемент - в качестве правого дочернего элемента. (Второй уровень - 2 элемента).
• Поместите следующие два элемента в качестве дочерних элементов левого узла второго уровня. Снова, поместите следующие два элемента как дочерние элементы правого узла второго уровня (3-й уровень - 4 элемента).
• Продолжайте повторять, пока не дойдете до последнего элемента.

Связь между индексами массива и элементами дерева

Полное бинарное дерево обладает интересным свойством, которое мы можем использовать для поиска дочерних элементов и родителей любого узла.
Если индекс любого элемента в массиве равен i, элемент в индексе 2i + 1 станет левым потомком, а элемент в индексе 2i + 2 станет правым потомком. Кроме того, родительский элемент любого элемента с индексом i задается нижней границей (i-1) / 2.

Проверим это:

Left child of 1 (index 0)
= element in (2*0+1) index 
= element in 1 index 
= 12


Right child of 1
= element in (2*0+2) index
= element in 2 index 
= 9

Similarly,
Left child of 12 (index 1)
= element in (2*1+1) index
= element in 3 index
= 5

Right child of 12
= element in (2*1+2) index
= element in 4 index
= 6

Также подтвердим, что правила верны для нахождения родителя любого узла:

Parent of 9 (position 2) 
= (2-1)/2 
= ½ 
= 0.5
~ 0 index 
= 1

Parent of 12 (position 1) 
= (1-1)/2 
= 0 index 
= 1

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

Что такое структура данных кучи?

Куча - это специальная древовидная структура данных. Говорят, что двоичное дерево следует структуре данных кучи, если

• это полное бинарное дерево;
• все узлы в дереве следуют тому свойству, что они больше своих потомков, то есть самый большой элемент находится в корне, и оба его потомка меньше, чем корень, и так далее. Такая куча называется убывающая куча (Max-Heap). Если вместо этого все узлы меньше своих потомков, это называется возрастающая куча (Min-Heap).

Слева на рисунке убывающая куча, справа - возрастающая куча.

Как выстроить дерево

Начиная с идеального бинарного дерева, мы можем изменить его, чтобы оно стало убывающим, запустив функцию heapify для всех неконечных элементов кучи.

Поскольку heapfiy использует рекурсию, это может быть трудно для понимания. Итак, давайте сначала подумаем о том, как бы вы сложили дерево из трех элементов.

heapify(array)
    Root = array[0]
    Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])
    if(Root != Largest)
          Swap(Root, Largest)

В приведенном выше примере показаны два сценария - один, в котором корень является самым большим элементом, и нам не нужно ничего делать. И еще один, в котором корень имеет дочерний элемент большего размера, и нам нужно было поменять их местами, чтобы сохранить свойство убывающей кучи.
Если вы раньше работали с рекурсивными алгоритмами, то вы поняли, что это должен быть базовый случай.

Теперь давайте подумаем о другом сценарии, в котором существует более одного уровня.

На рисунке оба поддерева корневого элемента второго уровня уже являются
убывающими кучами.
Верхний элемент не подходит под убывающую кучу, но все поддеревья являются убывабщими.
Чтобы сохранить свойство убывания для всего дерева, нам нужно будет "протолкнуть" родителя вниз, пока он не достигнет своей правильной позиции.

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

Мы можем объединить оба эти условия в одну функцию heapify следующим образом:

void heapify(int arr[], int n, int i)
{
   int largest = i;
   int l = 2*i + 1;
   int r = 2*i + 2;

   if (l < n && arr[l] > arr[largest])
     largest = l;

   if (right < n && arr[r] > arr[largest])
     largest = r;

   if (largest != i)
   {
     swap(arr[i], arr[largest]);

     // Recursively heapify the affected sub-tree
     heapify(arr, n, largest);
   }
}

Эта функция работает как для базового случая, так и для дерева любого размера. Таким образом, мы можем переместить корневой элемент в правильное положение, чтобы поддерживать статус убывающей кучи для любого размера дерева, пока поддеревья являются убывающими.

Сборка убывающей кучи

Чтобы собрать убывающую кучу из любого дерева, мы можем начать выстраивать каждое поддерево снизу вверх и получить убывающую кучу после применения функции ко всем элементам, включая корневой элемент.

В случае полного дерева первый индекс неконечного узла определяется как n / 2 - 1. Все остальные узлы после этого являются листовыми узлами и, следовательно, не нуждаются в куче.

Мы можем выстроить убывающую кучу так:

// Build heap (rearrange array)
   for (int i = n / 2 - 1; i >= 0; i--)
     heapify(arr, n, i);

Как показано на диаграмме выше, мы начинаем с кучи самых маленьких деревьев и постепенно продвигаемся вверх, пока не достигнем корневого элемента.

Процедуры для Heapsort

1. Поскольку дерево удовлетворяет свойству убывающей, самый большой элемент сохраняется в корневом узле.
2. Удалите корневой элемент и поместите в конец массива (n-я позиция). Поместите последний элемент дерева (кучу) в свободное место.
3. Уменьшите размер кучи на 1 и снова укрупните корневой элемент, чтобы у вас был самый большой элемент в корне.
4. Процесс повторяется до тех пор, пока все элементы списка не будут отсортированы.

Код выглядит так:

for (int i=n-1; i>=0; i--)
   {
     // Переместить текущий корень в конец
     swap(arr[0], arr[i]);

     // вызовите максимальный heapify на уменьшенной куче
     heapify(arr, i, 0);
   }

Представление

Сортировка кучи имеет O (nlogn) временные сложности для всех случаев (лучший случай, средний случай и худший случай). В чем же причина? Высота полного бинарного дерева, содержащего n элементов, равна log (n).

Как мы видели ранее, чтобы полностью накапливать элемент, чьи поддеревья уже являются убывабщими кучами, нам нужно продолжать сравнивать элемент с его левым и правым потомками и толкать его вниз, пока он не достигнет точки, где оба его потомка меньше его.

В худшем случае нам потребуется переместить элемент из корневого узла в конечный узел, выполнив несколько сравнений и обменов log (n).

На этапе build_max_heap мы делаем это для n / 2 элементов, поэтому сложность шага build_heap в наихудшем случае равна n / 2 * log (n) ~ nlogn.

На этапе сортировки мы обмениваем корневой элемент с последним элементом и подкачиваем корневой элемент. Для каждого элемента это снова занимает большое время, поскольку нам, возможно, придется перенести этот элемент от корня до листа. Поскольку мы повторяем операцию n раз, шаг heap_sort также nlogn.

Кроме того, поскольку шаги build_max_heap и heap_sort выполняются один за другим, алгоритмическая сложность не умножается и остается в порядке nlogn.

Также выполняется сортировка в O (1) пространстве сложности. По сравнению с быстрой сортировкой, в худшем случае (O (nlogn)). Быстрая сортировка имеет сложность O (n ^ 2) для худшего случая. Но в других случаях быстрая сортировка выполняется достаточно быстро. Introsort - это альтернатива heapsort, которая сочетает в себе quicksort и heapsort для сохранения преимуществ, таких как скорость heapsort в худшем случае и средняя скорость quicksort.

Применение сортировки кучей

Системы, связанные с безопасностью, и встроенные системы, такие как ядро ​​Linux, используют сортировку кучей из-за верхней границы O (n log n) времени работы Heapsort и постоянной верхней границы O (1) его вспомогательного хранилища.

Хотя сортировка кучей имеет O (n log n) временную сложность даже для наихудшего случая, у нее нет больше приложений (по сравнению с другими алгоритмами сортировки, такими как быстрая сортировка, сортировка слиянием). Тем не менее, его базовая структура данных, куча, может быть эффективно использована, если мы хотим извлечь наименьший (или наибольший) из списка элементов без дополнительных затрат на сохранение оставшихся элементов в отсортированном порядке. Например, приоритетные очереди.

Реализация сортировки кучи на разных языках программирования

Реализация C ++

// C++ program for implementation of Heap Sort
#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i)
{
   // Find largest among root, left child and right child
   int largest = i;
   int l = 2*i + 1;
   int r = 2*i + 2;

   if (l < n && arr[l] > arr[largest])
     largest = l;

   if (right < n && arr[r] > arr[largest])
     largest = r;

   // Swap and continue heapifying if root is not largest
   if (largest != i)
   {
     swap(arr[i], arr[largest]);
     heapify(arr, n, largest);
   }
}

// main function to do heap sort
void heapSort(int arr[], int n)
{
   // Build max heap
   for (int i = n / 2 - 1; i >= 0; i--)
     heapify(arr, n, i);

   // Heap sort
   for (int i=n-1; i>=0; i--)
   {
     swap(arr[0], arr[i]);

     // Heapify root element to get highest element at root again
     heapify(arr, i, 0);
   }
}

void printArray(int arr[], int n)
{
   for (int i=0; i<n; ++i)
     cout << arr[i] << " ";
   cout << "\n";
}

int main()
{
   int arr[] = {1,12,9,5,6,10};
   int n = sizeof(arr)/sizeof(arr[0]);
   heapSort(arr, n);

   cout << "Sorted array is \n";
   printArray(arr, n);
}

Реализация на Java

// Java program for implementation of Heap Sort
public class HeapSort
{   

    public void sort(int arr[])
    {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
          heapify(arr, n, i);
        }


        // Heap sort
        for (int i=n-1; i>=0; i--)
        {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Heapify root element
            heapify(arr, i, 0);
        }
    }

    void heapify(int arr[], int n, int i)
    {
        // Find largest among root, left child and right child
        int largest = i; 
        int l = 2*i + 1; 
        int r = 2*i + 2;  

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        // Swap and continue heapifying if root is not largest
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    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[] = {1,12,9,5,6,10};

        HeapSort hs = new HeapSort();
        hs.sort(arr);

        System.out.println("Sorted array is");
        printArray(arr);
    }
}

Реализация на Python (Python 3)

def heapify(arr, n, i):
    # Find largest among root and children
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2 

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    # If root is not largest, swap with largest and continue heapifying
    if largest != i:
        arr[i],arr[largest] = arr[largest],arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)

    # Build max heap
    for i in range(n, 0, -1):
        heapify(arr, n, i)


    for i in range(n-1, 0, -1):
        # swap
        arr[i], arr[0] = arr[0], arr[i]  

        #heapify root element
        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])