Алгоритм сортування купою

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])