Сортування купи це метод сортування на основі порівняння Бінарна купа структура даних. Це схоже на сортування вибору де ми спочатку знаходимо мінімальний елемент і розміщуємо мінімальний елемент на початку. Повторіть той самий процес для решти елементів.
Алгоритм сортування купи
Щоб вирішити проблему, дотримуйтеся наведеної нижче ідеї:
Команда запуску Linux
Рекомендована проблема. Будь ласка, спочатку розв’яжіть її на ПРАКТИЦІ, перш ніж переходити до вирішення проблемиСпочатку перетворіть масив у структуру даних купи за допомогою heapify, потім один за одним видаліть кореневий вузол Max-heap і замініть його останнім вузлом у купі, а потім heapify корінь купи. Повторюйте цей процес, доки розмір купи не перевищить 1.
- Створіть купу з заданого вхідного масиву.
- Повторюйте наступні кроки, поки купа не міститиме лише один елемент:
- Поміняти місцями кореневий елемент купи (який є найбільшим елементом) останнім елементом купи.
- Видаліть останній елемент купи (який зараз у правильному положенні).
- Нагромаджуйте елементи купи, що залишилися.
- Відсортований масив отримується зміною порядку елементів у вхідному масиві на зворотний.
Детальна робота сортування купи
Щоб більш чітко зрозуміти сортування купи, давайте візьмемо несортований масив і спробуємо відсортувати його за допомогою сортування купи.
Розглянемо масив: arr[] = {4, 10, 3, 5, 1}.Побудувати повне бінарне дерево: Побудуйте повне бінарне дерево з масиву.
Алгоритм сортування купи | Побудуйте повне бінарне дерево
Перетворення на максимальну купу: Після цього завдання полягає в тому, щоб побудувати дерево з цього несортованого масиву та спробувати його перетворити максимальна купа.
- Щоб перетворити купу в максимальну купу, батьківський вузол завжди повинен бути більшим або дорівнювати дочірнім вузлам
- Тут, у цьому прикладі, як батьківський вузол 4 менший за дочірній вузол 10, таким чином, поміняйте їх місцями, щоб створити максимальну купу.
- тепер, 4 як батько менший за дитину 5 , таким чином поміняйте їх обидва місцями, і отримана купа та масив мають бути такими:
Алгоритм сортування купи | Макс Хепафай побудував бінарне дерево
Виконайте сортування купи: Видаліть максимальний елемент на кожному кроці (тобто перемістіть його в кінцеве положення та видаліть його), а потім розгляньте решту елементів і перетворите їх на максимальну купу.
- Видаліть кореневий елемент (10) з максимальної купи. Щоб видалити цей вузол, спробуйте поміняти його місцями з останнім вузлом, тобто. (1). Після видалення кореневого елемента знову об’єднайте його, щоб перетворити на максимальну купу.
- Отримана купа та масив мають виглядати так:
Алгоритм сортування купи | Видалити максимум з кореня та максимально збільшити
- Повторіть описані вище кроки, і це буде виглядати так:
Алгоритм сортування купи | Видалити наступний максимум із кореня nad max heapify
- Тепер знову видаліть корінь (тобто 3) і виконайте heapify.
Алгоритм сортування купи | Повторити попередній крок
паралельна обробка
- Тепер, коли корінь знову видаляється, він сортується. і відсортований масив буде таким arr[] = {1, 3, 4, 5, 10} .
Алгоритм сортування купи | Остаточний відсортований масив
довжина рядка bash
Реалізація Heap Sort
C++ // C++ program for implementation of Heap Sort #include using namespace std; // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) { // Initialize largest as root int largest = i; // left = 2*i + 1 int l = 2 * i + 1; // right = 2*i + 2 int r = 2 * i + 2; // If left child is larger than root if (l < N && arr[l]>arr[найбільший]) найбільший = l; // Якщо правий дочірній елемент більший за найбільший // поки if (r< N && arr[r]>arr[найбільший]) найбільший = r; // Якщо найбільше не є коренем if (largest != i) { swap(arr[i], arr[largest]); // Рекурсивне нагромадження ураженого // піддерева heapify(arr, N, larger); } } // Основна функція для сортування купи void heapSort(int arr[], int N) { // Побудувати купу (перевпорядкувати масив) для (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Один за одним витягти елемент // із купи for (int i = N - 1; i> 0; i--) { // Перемістити поточний корінь до кінця swap(arr[0], arr[i]); // виклик max heapify на зменшеній купі heapify(arr, i, 0); } } // Допоміжна функція для друку масиву розміром n void printArray(int arr[], int N) { for (int i = 0; i< N; ++i) cout << arr[i] << ' '; cout << '
'; } // Driver's code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call heapSort(arr, N); cout << 'Sorted array is
'; printArray(arr, N); }> C // Heap Sort in C #include // Function to swap the position of two elements void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) { // Find largest among root, // left child and right child // Initialize largest as root int largest = i; // left = 2*i + 1 int left = 2 * i + 1; // right = 2*i + 2 int right = 2 * i + 2; // If left child is larger than root if (left < N && arr[left]>arr[найбільший]) найбільший = ліворуч; // Якщо правий дочірній елемент більший за найбільший // поки якщо (правий< N && arr[right]>arr[найбільший]) найбільший = правий; // Поміняти місцями та продовжити об’єднання // якщо корінь не найбільший // Якщо найбільший не є коренем if (largest != i) { swap(&arr[i], &arr[largest]); // Рекурсивне нагромадження ураженого // піддерева heapify(arr, N, larger); } } // Основна функція для сортування купи void heapSort(int arr[], int N) { // Створення максимальної купи для (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, i); // Сортування купи для (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]); // Heapify кореневий елемент // щоб знову отримати найвищий елемент // root heapify(arr, i, 0); } } // Допоміжна функція для друку масиву розміром n void printArray(int arr[], int N) { for (int i = 0; i< N; i++) printf('%d ', arr[i]); printf('
'); } // Driver's code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call heapSort(arr, N); printf('Sorted array is
'); printArray(arr, N); } // This code is contributed by _i_plus_plus_.> Java // Java program for implementation of Heap Sort public class HeapSort { public void sort(int arr[]) { int N = arr.length; // Build heap (rearrange array) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Один за одним витягти елемент із купи for (int i = N - 1; i> 0; i--) { // Перемістити поточний корінь у кінець int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // виклик max heapify на зменшеній купі heapify(arr, i, 0); } } // Щоб об’єднати піддерево з коренем у вузол i, який // є індексом в arr[]. n — розмір купи void heapify(int arr[], int N, int i) { int large = i; // Ініціалізація найбільшого як кореня int l = 2 * i + 1; // ліворуч = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // Якщо лівий дочірній елемент більший за корінь if (l< N && arr[l]>arr[найбільший]) найбільший = l; // Якщо правий дочірній елемент більший за найбільший на даний момент if (r< N && arr[r]>arr[найбільший]) найбільший = r; // Якщо найбільше не є коренем if (largest != i) { int swap = arr[i]; arr[i] = arr[найбільший]; arr[найбільший] = обмін; // Рекурсивне нагромадження ураженого піддерева heapify(arr, N, larger); } } /* Допоміжна функція для друку масиву розміром n */ static void printArray(int arr[]) { int N = arr.length; для (int i = 0; i< N; ++i) System.out.print(arr[i] + ' '); System.out.println(); } // Driver's code public static void main(String args[]) { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = arr.length; // Function call HeapSort ob = new HeapSort(); ob.sort(arr); System.out.println('Sorted array is'); printArray(arr); } }> C# // C# program for implementation of Heap Sort using System; public class HeapSort { public void sort(int[] arr) { int N = arr.Length; // Build heap (rearrange array) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Один за одним витягти елемент із купи for (int i = N - 1; i> 0; i--) { // Перемістити поточний корінь у кінець int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // виклик max heapify на зменшеній купі heapify(arr, i, 0); } } // Щоб об’єднати піддерево з коренем у вузол i, який // є індексом в arr[]. n — розмір купи void heapify(int[] arr, int N, int i) { int larger = i; // Ініціалізація найбільшого як кореня int l = 2 * i + 1; // ліворуч = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // Якщо лівий дочірній елемент більший за корінь if (l< N && arr[l]>arr[найбільший]) найбільший = l; // Якщо правий дочірній елемент більший за найбільший на даний момент if (r< N && arr[r]>arr[найбільший]) найбільший = r; // Якщо найбільше не є коренем if (largest != i) { int swap = arr[i]; arr[i] = arr[найбільший]; arr[найбільший] = обмін; // Рекурсивне нагромадження ураженого піддерева heapify(arr, N, larger); } } /* Допоміжна функція для друку масиву розміром n */ static void printArray(int[] arr) { int N = arr.Length; для (int i = 0; i< N; ++i) Console.Write(arr[i] + ' '); Console.Read(); } // Driver's code public static void Main() { int[] arr = { 12, 11, 13, 5, 6, 7 }; int N = arr.Length; // Function call HeapSort ob = new HeapSort(); ob.sort(arr); Console.WriteLine('Sorted array is'); printArray(arr); } } // This code is contributed // by Akanksha Rai(Abby_akku)> Javascript // JavaScript program for implementation // of Heap Sort function sort( arr) { var N = arr.length; // Build heap (rearrange array) for (var i = Math.floor(N / 2) - 1; i>= 0; i--) heapify(arr, N, i); // Один за одним витягти елемент із купи for (var i = N - 1; i> 0; i--) { // Перемістити поточний корінь у кінець var temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // виклик max heapify на зменшеній купі heapify(arr, i, 0); } } // Щоб об’єднати піддерево з коренем у вузол i, який // є індексом в arr[]. n — розмір функції купи heapify(arr, N, i) { var larger = i; // Ініціалізація найбільшого як кореня var l = 2 * i + 1; // ліворуч = 2*i + 1 var r = 2 * i + 2; // right = 2*i + 2 // Якщо лівий дочірній елемент більший за корінь if (l< N && arr[l]>arr[найбільший]) найбільший = l; // Якщо правий дочірній елемент більший за найбільший на даний момент if (r< N && arr[r]>arr[найбільший]) найбільший = r; // Якщо найбільше не є коренем if (largest != i) { var swap = arr[i]; arr[i] = arr[найбільший]; arr[найбільший] = обмін; // Рекурсивне нагромадження ураженого піддерева heapify(arr, N, larger); } } /* Допоміжна функція для друку масиву розміром n */ function printArray(arr) { var N = arr.length; для (перемінна i = 0; i< N; ++i) document.write(arr[i] + ' '); } var arr = [12, 11, 13, 5, 6, 7]; var N = arr.length; sort(arr); document.write( 'Sorted array is'); printArray(arr, N); // This code is contributed by SoumikMondal> PHP // Php program for implementation of Heap Sort // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap function heapify(&$arr, $N, $i) { $largest = $i; // Initialize largest as root $l = 2*$i + 1; // left = 2*i + 1 $r = 2*$i + 2; // right = 2*i + 2 // If left child is larger than root if ($l < $N && $arr[$l]>$arr[$largest]) $largest = $l; // Якщо правий дочірній елемент більший за найбільший if ($r< $N && $arr[$r]>$arr[$largest]) $largest = $r; // Якщо найбільше не є коренем if ($largest != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$largest]; $arr[$largest] = $swap; // Рекурсивне нагромадження ураженого піддерева heapify($arr, $N, $largest); } } // основна функція для сортування купи function heapSort(&$arr, $N) { // Побудувати купу (перевпорядкувати масив) для ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // Один за одним витягти елемент із купи for ($i = $N-1; $i> 0; $i--) { // Перемістити поточний корінь до кінця $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // викликати max heapify на зменшеній купі heapify($arr, $i, 0); } } /* Допоміжна функція для друку масиву розміром n */ function printArray(&$arr, $N) { for ($i = 0; $i)< $N; ++$i) echo ($arr[$i].' ') ; } // Driver's program $arr = array(12, 11, 13, 5, 6, 7); $N = sizeof($arr)/sizeof($arr[0]); // Function call heapSort($arr, $N); echo 'Sorted array is ' . '
'; printArray($arr , $N); // This code is contributed by Shivi_Aggarwal ?>> Python3 # Python program for implementation of heap Sort # To heapify subtree rooted at index i. # n is size of heap def heapify(arr, N, i): largest = i # Initialize largest as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 # See if left child of root exists and is # greater than root if l < N and arr[largest] < arr[l]: largest = l # See if right child of root exists and is # greater than root if r < N and arr[largest] < arr[r]: largest = r # Change root, if needed if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # swap # Heapify the root. heapify(arr, N, largest) # The main function to sort an array of given size def heapSort(arr): N = len(arr) # Build a maxheap. for i in range(N//2 - 1, -1, -1): heapify(arr, N, i) # One by one extract elements for i in range(N-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # swap heapify(arr, i, 0) # Driver's code if __name__ == '__main__': arr = [12, 11, 13, 5, 6, 7] # Function call heapSort(arr) N = len(arr) print('Sorted array is') for i in range(N): print('%d' % arr[i], end=' ') # This code is contributed by Mohit Kumra> Вихід
Sorted array is 5 6 7 11 12 13>
Аналіз складності Сортування купи
Часова складність: O(N log N)
Допоміжний простір: O(log n), через рекурсивний стек викликів. Однак допоміжний простір може бути O(1) для ітеративної реалізації.
Важливі моменти щодо Heap Sort:
- Сортування купи — це алгоритм на місці.
- Його типова реалізація не є стабільною, але її можна зробити стабільною (див це )
- Зазвичай у 2-3 рази повільніше, ніж добре реалізовано Швидке сортування . Причиною повільності є недостатня локальність посилання.
Переваги Heap Sort:
- Ефективна складність часу: Сортування купи має часову складність O(n log n) у всіх випадках. Це робить його ефективним для сортування великих наборів даних. The log n Фактор походить від висоти бінарної купи, і він гарантує, що алгоритм підтримує хорошу продуктивність навіть із великою кількістю елементів.
- Використання пам'яті – Використання пам’яті може бути мінімальним (шляхом написання ітеративного heapify() замість рекурсивного). Таким чином, окрім того, що необхідно для зберігання початкового списку елементів для сортування, йому не потрібен додатковий простір пам’яті для роботи
- Простота – Його простіше зрозуміти, ніж інші настільки ж ефективні алгоритми сортування, оскільки він не використовує передові концепції інформатики, такі як рекурсія.
Недоліки Heap Sort:
- Дорого : Сортування купи є дорогим, оскільки константи вищі порівняно з сортуванням злиттям, навіть якщо часова складність становить O(n Log n) для обох.
- Нестабільний : сортування купи нестабільне. Це може змінити відносний порядок.
- Ефективний: Heap Sort не дуже ефективний під час роботи з дуже складними даними.
Часті запитання щодо сортування купи
Q1. Які дві фази сортування купи?
Алгоритм сортування купи складається з двох етапів. На першому етапі масив перетворюється на максимальну купу. А на другому етапі найвищий елемент видаляється (тобто той, що знаходиться в корені дерева), а елементи, що залишилися, використовуються для створення нової максимальної купи.
Q2. Чому Heap Sort не є стабільним?
Алгоритм сортування купи не є стабільним алгоритмом, тому що ми міняємо arr[i] на arr[0] у heapSort(), що може змінити відносний порядок еквівалентних ключів.
Q3. Чи є Heap Sort прикладом алгоритму «Розділяй і володарюй»?
Сортування купи є НІ взагалі алгоритм «Розділяй і володарюй». Він використовує структуру даних купи для ефективного сортування свого елемента, а не підхід розділяй і володарюй для сортування елементів.
Q4. Який алгоритм сортування кращий – Heap sort або Merge Sort?
дискета
Відповідь полягає в порівнянні їхньої складності в часі та вимог до простору. Сортування злиттям трохи швидше, ніж сортування купи. Але, з іншого боку, сортування злиттям займає додаткову пам’ять. Залежно від вимоги слід вибрати, який з них використовувати.
Q5. Чому сортування купи краще, ніж сортування виділення?
Сортування купи схоже на сортування вибору, але з кращим способом отримати максимальний елемент. Він використовує переваги структури даних купи, щоб отримати максимальний елемент за постійний час