Алгоритм сортування купи (з Code in Python та C++)
Сара Чен
⚡ Розумний підсумок
Алгоритм сортування купою сортує масив, створюючи двійкову купу та багаторазово використовуючиtracвведення його кореневого значення в відсортовану секцію. У цьому ресурсі пояснюються heapify, купи max та min, псевдокод та complete Python та C++ реалізації з аналізом часової складності.
Що таке алгоритм сортування купи?
Сортування купою – один із популярних та швидших алгоритмів сортування. Він побудований на повній структурі даних бінарного дерева. Ми шукатимемо максимальний елемент і розміщуватимемо його на вершині максимальної купи. Ми розмістимо його на батьківському вузлі бінарного дерева.
Скажімо, дано масив, дані = [10,5, 7, 9, 4, 11, 45, 17, 60].
У масиві, якщо i-й (i=0,1,2,3 …) індекс є батьківським вузлом, тоді (2i+1) і (2i+2) будуть лівим і правим нащадками. Створення повного бінарного дерева з цим масивом виглядатиме так:
Ми зробимо процес heapify від початку до кінця масиву. Спочатку, якщо ми перетворимо масив на дерево, він виглядатиме так, як показано вище. Ми бачимо, що він не підтримує жодних властивостей купи (мінімальна купа або максимальна купа). Ми отримаємо відсортований масив, виконавши процес heapify для всіх вузлів.
Застосування Heap Sort
Ось деякі випадки використання алгоритму сортування купи:
- Побудова «пріоритетних черг» вимагає сортування купи. Оскільки heapsort зберігає елемент відсортованим після кожної вставки.
- Структура даних купи є ефективною для пошуку kth найбільший елемент у даному масиві.
- Ядро 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).
Примітка: Щоб створити відсортований масив, нам потрібно замінити вузол із максимальним значенням на його наступника.
Цей процес називається «extract макс”. Оскільки 60 є максимальним вузлом, ми зафіксуємо його позицію до 0-го індексу та створимо купу без вузла 60.
Крок 7) Оскільки 60 видалено, наступне максимальне значення дорівнює 45. Ми виконаємо процес «Прикладtrac«t Max» знову з вузла 45.
Цього разу ми отримаємо 45 і замінимо кореневий вузол його наступником 17.
Нам потрібно виконати "Extract Макс”, поки всі елементи не будуть відсортовані.
Після виконання цих кроків, поки ми неtract усі максимальні значення, ми отримаємо наступний масив.
Що таке бінарна купа?
Бінарна купа є різновидом повної двійкове дерево структура даних. У такій структурі дерева батьківський вузол або більший, або менший за дочірні вузли. Якщо батьківський вузол менший, то купа називається «мінімальна купа», а якщо батьківський вузол більший, купа називається «максимальна купа».
Ось приклади мінімальної та максимальної купи.
На наведеному вище малюнку, якщо ви помітили «Мінімальна купа», батьківський вузол завжди менший за дочірні вузли. У голові дерева ми можемо знайти найменше значення 10.
Подібним чином, для «максимальної купи» батьківський вузол завжди більший за дочірні вузли. Максимальний елемент присутній у головному вузлі для «Максимальної купи».
Що таке «Heapify»?
«Heapify» — це принцип купи, який забезпечує положення вузла. У Heapify максимальна купа завжди підтримує зв’язок із батьківським і дочірнім вузлом, і це означає, що батьківський вузол буде більшим за дочірні вузли.
Наприклад, якщо додається новий вузол, нам потрібно змінити форму купи. Однак, можливо, нам доведеться змінити або поміняти місцями вузли або перевпорядкувати масив. Цей процес переформатуванняping купа називається «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)
Псевдо Code для сортування купою
Ось псевдокод для алгоритму сортування купи:
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)
Приклад сортування купою Code in 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
Приклад сортування купою Code in 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, буде висота або загальний рівень Ввійти2(n). Отже, вставлення одного елемента може зайняти максимум Log(n) ітерацій.
Коли ми хочемо отримати максимальне значення з купи, ми просто беремо кореневий вузол. Потім знову запустіть heapify. Кожна купа бере Ввійти2(n) час. КолишнійtracДосягнення максимуму займає час O(1).
Найкращий випадок складності часу для алгоритму сортування купи
Коли всі елементи вже відсортовані в масиві, для створення купи знадобиться O(n) часу. Тому що, якщо список відсортований, то вставлення елемента займе постійний час, тобто O(1).
Отже, у найкращому випадку для створення максимальної або мінімальної купи знадобиться O(n) часу.
Середня складність випадку для алгоритму сортування купи
Вставка елемента або експозиціїtracВизначення максимуму коштує O(log(n)) часу. Отже, середня складність часу для алгоритму сортування купи становить O(n log(n)).
Найгірший випадок складності часу для алгоритму сортування купи
Подібно до середнього випадку, у найгіршому випадку ми можемо виконати heapify n разів. Кожне heapify коштуватиме O(log(n)) часу. Отже, найгірша часова складність буде O(n log(n)).
Складність простору для алгоритму сортування купи
Сортування купи — це розроблений на місці алгоритм. Це означає, що для виконання завдання не потрібна додаткова або тимчасова пам'ять. Якщо ми побачимо реалізацію, то помітимо, що ми використовували swap () для здійснення обміну вузлами. Ніякий інший список чи масив не був потрібен. Отже, складність простору дорівнює O(1).
