Алгоритм сортування купи (з кодом у Python та C++)

Що таке алгоритм сортування купи?

Heap Sort — один із популярних і швидших алгоритмів сортування. Він побудований на повній структурі даних бінарного дерева. Ми шукатимемо максимальний елемент і розмістимо його на вершині для максимальної купи. Ми розмістимо його на батьківському вузлі бінарного дерева.

Скажімо, дано масив, дані = [10,5, 7, 9, 4, 11, 45, 17, 60].

У масиві, якщо i-й (i=0,1,2,3 …) індекс є батьківським вузлом, тоді (2i+1) і (2i+2) будуть лівим і правим нащадками. Створення повного бінарного дерева з цим масивом виглядатиме так:

Ми зробимо процес heapify від початку до кінця масиву. Спочатку, якщо ми перетворимо масив на дерево, він виглядатиме так, як показано вище. Ми бачимо, що він не підтримує жодних властивостей купи (мінімальна купа або максимальна купа). Ми отримаємо відсортований масив, виконавши процес heapify для всіх вузлів.

Застосування Heap Sort

Ось деякі випадки використання алгоритму сортування купи:

Побудова «пріоритетних черг» вимагає сортування купи. Оскільки heapsort зберігає елемент відсортованим після кожної вставки.
Структура даних купи є ефективною для пошуку k^th найбільший елемент у даному масиві.
Ядро Linux використовує сортування купи за замовчуванням алгоритм сортування оскільки він має просторову складність O (1).

Створіть сортування купи з прикладом

Тут ми побудуємо максимальну купу з наступного повного бінарного дерева.

Листові вузли 17, 60, 4, 11 і 45. Вони не мають дочірніх вузлів. Тому вони є листовими вузлами. Отже, ми запустимо метод heapify з їх батьківського вузла. Ось кроки:

Крок 1) Виберіть крайнє піддерево зліва. Якщо дочірніх вузлів більше, поміняйте батьківський вузол дочірнім вузлом.

Тут батьківський вузол — 9. А дочірні — 17 і 60. Оскільки 60 є найбільшим, 60 і 9 буде поміняно місцями, щоб зберегти макс.

Крок 2) Тепер крайнє ліве піддерево нагромаджено. Наступний батьківський вузол — 7. Цей батьківський вузол має два дочірніх вузла, а найбільший — 45. Отже, 45 і 7 буде поміняно місцями.

Крок 3) Вузли 60 і 4 мають батьківський вузол 5. Оскільки «5» менший за дочірній вузол 60, його буде поміняно місцями.

Крок 4) Тепер вузол 5 має дочірній вузол 17,9. Це не підтримує властивість максимальної купи. Отже, 5 буде замінено на 17.

Крок 5) Вузол 10 буде замінено на 60, а потім на 17. Процес виглядатиме так.

Крок 6) До кроку 5 ми створили максимальну купу. Кожен батьківський вузол більший за дочірні вузли. Кореневий вузол має максимальне значення (60).

Примітка: Щоб створити відсортований масив, нам потрібно замінити вузол із максимальним значенням на його наступника.

Цей процес називається «витяжка макс”. Оскільки 60 є максимальним вузлом, ми зафіксуємо його позицію до 0-го індексу та створимо купу без вузла 60.

Крок 7) Оскільки 60 видалено, наступним максимальним значенням стане 45. Ми знову виконаємо процес «Вилучити максимум» із вузла 45.

Цього разу ми отримаємо 45 і замінимо кореневий вузол його наступником 17.

Нам потрібно виконати "Екстракт Макс”, поки всі елементи не будуть відсортовані.

Після виконання цих кроків, поки ми не витягнемо всі максимальні значення, ми отримаємо наступний масив.

Що таке бінарна купа?

Бінарна купа є різновидом повної двійкове дерево структура даних. У такій структурі дерева батьківський вузол або більший, або менший за дочірні вузли. Якщо батьківський вузол менший, то купа називається «мінімальна купа», а якщо батьківський вузол більший, купа називається «максимальна купа».

Ось приклади мінімальної та максимальної купи.

На наведеному вище малюнку, якщо ви помітили «Мінімальна купа», батьківський вузол завжди менший за дочірні вузли. У голові дерева ми можемо знайти найменше значення 10.

Подібним чином, для «максимальної купи» батьківський вузол завжди більший за дочірні вузли. Максимальний елемент присутній у головному вузлі для «Максимальної купи».

Що таке «Heapify»?

«Heapify» — це принцип купи, який забезпечує положення вузла. У Heapify максимальна купа завжди підтримує зв’язок із батьківським і дочірнім вузлом, і це означає, що батьківський вузол буде більшим за дочірні вузли.

Наприклад, якщо додається новий вузол, нам потрібно змінити форму купи. Однак нам може знадобитися змінити або поміняти місцями вузли або перевпорядкувати масив. Цей процес зміни форми купи називається «heapify».

Ось приклад роботи heapify:

Додавання нового вузла та Heapify — Додавання нового вузла та heapify

Ось кроки для heapify:

Крок 1) Додано вузол 65 як правого дочірнього вузла 60.

Крок 2) Перевірте, чи щойно доданий вузол більший за батьківський.

Крок 3) Оскільки він більший за батьківський вузол, ми поміняли правий дочірній вузол з його батьківським.

Як побудувати купу

Перш ніж будувати купу або складати дерево, нам потрібно знати, як ми будемо її зберігати. Оскільки купа є повним бінарним деревом, краще використовувати an масив для зберігання даних купи.

Скажімо, масив містить n елементів. Якщо «i»-й індекс є батьківським вузлом, то лівий вузол буде в індексі (2i+1), а правий вузол буде за індексом (2i+2). Ми припускаємо, що індекс масиву починається з 0.

Використовуючи це, давайте збережемо максимальну купу в наступному масиві:

Представлення максимальної купи на основі масиву

Алгоритм heapify підтримує властивість heap. Якщо батьківський вузол не має екстремального значення (меншого чи більшого), його буде замінено на найбільш крайній дочірній вузол.

Ось кроки для об’єднання максимальної купи:

Крок 1) Почніть з вузла листа.

Крок 2) Знайдіть максимум між батьком і дітьми.

Крок 3) Поміняйте вузли місцями, якщо дочірній вузол має більше значення, ніж батьківський.

Крок 4) Підніміться на один рівень вище.

Крок 5) Виконуйте кроки 2,3,4, 0, XNUMX, поки не досягнете індексу XNUMX або відсортуйте все дерево.

Ось псевдокод для рекурсивного heapify (макс. купа):

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

Псевдокод для сортування купи

Ось псевдокод для алгоритму сортування купи:

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

Приклад коду сортування купи в C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

вихід:

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

Приклад коду сортування купи в Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

вихід:

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

Аналіз часової та просторової складності сортування купи

Для сортування купи ми можемо проаналізувати часову складність і просторову складність. Для часової складності ми маємо такі випадки:

Найкращий випадок
Середній випадок
Найгірший випадок

Купа реалізована на повному бінарному дереві. Отже, на нижньому рівні бінарного дерева буде максимальна кількість вузлів. Якщо нижній рівень має n вузлів, то верхній рівень матиме n/2 вузлів.

У цьому прикладі рівень 3 містить чотири елементи, рівень 2 має два предмети, а рівень 1 має один предмет. Якщо є загальна кількість елементів n, буде висота або загальний рівень Ввійти₂(n). Отже, вставлення одного елемента може зайняти максимум Log(n) ітерацій.

Коли ми хочемо отримати максимальне значення з купи, ми просто беремо кореневий вузол. Потім знову запустіть heapify. Кожна купа бере Ввійти₂(n) час. Вилучення максимуму займає O(1) часу.

Найкращий випадок складності часу для алгоритму сортування купи

Коли всі елементи вже відсортовані в масиві, для створення купи знадобиться O(n) часу. Тому що, якщо список відсортований, то вставлення елемента займе постійний час, тобто O(1).

Отже, у найкращому випадку для створення максимальної або мінімальної купи знадобиться O(n) часу.

Середня складність випадку для алгоритму сортування купи

Вставлення елемента або вилучення максимуму коштує O(log(n)) часу. Отже, середня складність випадку для алгоритму сортування купи становить O(n log(n)).

Найгірший випадок складності часу для алгоритму сортування купи

Подібно до середнього випадку, у найгіршому випадку ми можемо виконати heapify n разів. Кожне heapify коштуватиме O(log(n)) часу. Отже, найгірша часова складність буде O(n log(n)).

Складність простору для алгоритму сортування купи

Сортування купи — це розроблений на місці алгоритм. Це означає, що для виконання завдання не потрібна додаткова або тимчасова пам'ять. Якщо ми побачимо реалізацію, то помітимо, що ми використовували swap () для здійснення обміну вузлами. Ніякий інший список чи масив не був потрібен. Отже, складність простору дорівнює O(1).