У цьому підручнику ви дізнаєтесь, як працює алгоритм сортування купи. Крім того, ви знайдете робочі приклади сортування купи у C, C ++, Java та Python.
Heap Sort - популярний та ефективний алгоритм сортування в комп'ютерному програмуванні. Навчання написанню алгоритму сортування купи вимагає знання двох типів структур даних - масивів та дерев.
Початковий набір чисел, які ми хочемо сортувати, зберігається в масиві, наприклад, (10, 3, 76, 34, 23, 32)і після сортування ми отримуємо відсортований масив(3,10,23,32,34,76)
Сортування купи працює шляхом візуалізації елементів масиву як особливого виду повного двійкового дерева, званого купою.
Як обов’язкову умову, ви повинні знати про повне двійкове дерево та структуру даних купи.
Взаємозв'язок між індексами масивів та елементами дерева
Повне двійкове дерево має цікаву властивість, за допомогою якої ми можемо знайти дітей та батьків будь-якого вузла.
Якщо індекс будь-якого елемента в масиві дорівнює i, елемент в індексі 2i+1стане лівим дочірнім елементом, а елемент в 2i+2індексі - правильним дочірнім. Крім того, батьківський елемент будь-якого елемента з індексом i задається нижньою межею (i-1)/2.
Зв'язок між індексами масиву та купи
Давайте перевіримо це,
Лівий дочірній елемент 1 (індекс 0) = елемент у (2 * 0 + 1) індекс = елемент в 1 індекс = 12 Правий дочірній елемент 1 = елемент у (2 * 0 + 2) індекс = елемент у 2 індекс = 9 Аналогічно, Ліва дочірня частина 12 (індекс 1) = елемент у (2 * 1 + 1) індекс = елемент у 3 індекс = 5 Права дочірня частина 12 = елемент у (2 * 1 + 2) індекс = елемент у 4 індекс = 6
Давайте також підтвердимо, що правила діють для пошуку батьків будь-якого вузла
Батько 9 (позиція 2) = (2-1) / 2 = ½ = 0,5 ~ 0 індекс = 1 Батько 12 (позиція 1) = (1-1) / 2 = 0 індекс = 1
Розуміння цього зіставлення індексів масиву з позиціями дерева є критичним для розуміння того, як працює структура даних кучі та як вона використовується для реалізації сортування купи.
Що таке структура даних купи?
Heap - це спеціальна деревоподібна структура даних. Кажуть, що двійкове дерево має структуру даних купи, якщо
- це повне двійкове дерево
- Усі вузли у дереві дотримуються властивості, що вони більші за своїх дочірніх елементів, тобто найбільший елемент знаходиться в корені, і як його діти, так і менший за корінь тощо. Така купа називається max-heap. Якщо замість цього всі вузли менші за їхні діти, це називається min-heap
На наступному прикладі діаграми показано Max-Heap та Min-Heap.
Max Heap і Min Heap
Щоб дізнатись більше про це, відвідайте Структура даних купи.
Як «звалити» дерево
Починаючи з повного бінарного дерева, ми можемо змінити його, щоб він став Max-Heap, запустивши функцію, яка називається heapify, на всіх нелистових елементах купи.
Оскільки heapify використовує рекурсію, це може бути важко зрозуміти. Тож давайте спочатку подумаємо про те, як би ви нагромадили дерево лише трьома елементами.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Підсилюйте базові випадки
У наведеному вище прикладі показано два сценарії - один, в якому корінь є найбільшим елементом, і нам не потрібно нічого робити. І ще одна, в якій у кореня в дитинстві був більший елемент, і нам потрібно було поміняти місцями, щоб підтримувати властивість max-heap.
Якщо ви вже працювали з рекурсивними алгоритмами, ви, мабуть, визначили, що це має бути базовий випадок.
А тепер давайте подумаємо про інший сценарій, коли існує більше одного рівня.
Як сформувати кореневий елемент, коли його піддерева вже мають максимум куп
Верхній елемент - це не максимальна купа, але всі піддерева - це максимальна маса.
Щоб зберегти властивість max-heap для всього дерева, нам доведеться продовжувати натискати 2 вниз, поки воно не досягне свого правильного положення.
Як сформувати кореневий елемент, коли його піддерева - це макс-купи
Таким чином, щоб зберегти властивість max-heap у дереві, де обидва піддерева є max-купи, нам потрібно повторно запускати heapify на кореневому елементі, поки він не буде більшим за своїх дочірніх елементів або він стане листовим вузлом.
Ми можемо поєднати обидві ці умови в одній функції посилення, як
void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) )
Ця функція працює як для базового випадку, так і для дерева будь-якого розміру. Таким чином, ми можемо перемістити кореневий елемент у правильне положення, щоб зберегти статус max-heap для будь-якого розміру дерева до тих пір, поки піддерева не перевищують маси.
Побудуйте max-heap
Щоб побудувати max-heap з будь-якого дерева, ми можемо, таким чином, розпочати скупчення кожного піддерева знизу вгору і закінчити max-heap після того, як функція застосована до всіх елементів, включаючи кореневий елемент.
У разі повного дерева перший індекс нелистового вузла задається як n/2 - 1. Усі інші вузли після цього є листовими вузлами, і тому їх не потрібно скупчувати.
Отже, ми можемо створити максимум купи як
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Створити масив і обчислити i 
Кроки для побудови максимальної купи для сортування купи 
Кроки для побудови максимальної купи для сортування купи 
Кроки для побудови максимальної купи для сортування купи
Як показано на наведеній вище схемі, ми починаємо з нагромадження найменших найменших дерев і поступово рухаємося вгору, поки не дійдемо до кореневого елемента.
Якщо ви до цього часу все зрозуміли, вітаємо, ви на шляху до освоєння сорту Куча.
Як працює сортування купи?
- Оскільки дерево задовольняє властивості Max-Heap, тоді найбільший елемент зберігається в кореневому вузлі.
- Підкачка: Видаліть кореневий елемент і поставте в кінець масиву (n-те місце) Поставте останній елемент дерева (куча) у вільне місце.
- Видалити: зменшіть розмір купи на 1.
- Heapify: Знову підсиліть кореневий елемент, щоб ми мали найвищий елемент у корені.
- Процес повторюється до тих пір, поки всі елементи списку не будуть відсортовані.
Поміняти місцями, вилучити та підсилити
У наведеному нижче коді показано операцію.
// 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); )
Приклади Python, Java та C / C ++
Python Java C C ++ # Heap Sort in python 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//2, -1, -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 = (1, 12, 9, 5, 6, 10) heapSort(arr) n = len(arr) print("Sorted array is") for i in range(n): print("%d " % arr(i), end='')
// Heap Sort in Java 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 arr(largest)) largest = l; if (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); ) ) // Function to print an array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver code 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); ) )
// Heap Sort in C #include // Function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // 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); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) printf("%d ", arr(i)); printf(""); ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); printf("Sorted array is "); printArray(arr, n); )
// Heap Sort in C++ #include using namespace std; void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // 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); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) cout << arr(i) << " "; cout << ""; ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); cout << "Sorted array is "; printArray(arr, n); )
Складність сортування купи
Heap Sort має O(nlog n)часові складності для всіх випадків (найкращий випадок, середній випадок та найгірший випадок).
Давайте зрозуміємо причину. Висота повного двійкового дерева, що містить n елементів, дорівнюєlog n
As we have seen earlier, to fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it.
In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps.
During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log n ~ nlog n.
During the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes log n worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is also nlog n.
Also since the build_max_heap and heap_sort steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of nlog n.
Also it performs sorting in O(1) space complexity. Compared with Quick Sort, it has a better worst case ( O(nlog n) ). Quick Sort has complexity O(n^2) for worst case. But in other cases, Quick Sort is fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.
Heap Sort Applications
Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort's running time and constant O(1) upper bound on its auxiliary storage.
Незважаючи на те, що Heap Sort має O(n log n)складність у часі навіть у гіршому випадку, у нього немає більше додатків (порівняно з іншими алгоритмами сортування, такими як Quick Sort, Merge Sort). Однак основну структуру даних, купу, можна ефективно використовувати, якщо ми хочемо витягти найменший (або найбільший) зі списку елементів без накладних витрат на збереження решти елементів у відсортованому порядку. Наприклад, для пріоритетних черг.
