У цій статті ми обговоримо алгоритм Heapsort. Сортування купи обробляє елементи шляхом створення мінімальної або максимальної купи з використанням елементів заданого масиву. Мінімальна купа або максимальна купа представляє порядок масиву, у якому кореневий елемент представляє мінімальний або максимальний елемент масиву.
Сортування купи в основному рекурсивно виконує дві основні операції -
- Побудуйте купу H, використовуючи елементи масиву.
- Повторно видаліть кореневий елемент купи, сформованої в 1вулфаза.
Перш ніж дізнатися більше про сортування купи, давайте спочатку подивимося короткий опис Купа.
Що таке купа?
Купа — це повне бінарне дерево, а бінарне дерево — це дерево, у якому вузол може мати щонайбільше двох дітей. Повне двійкове дерево — це двійкове дерево, у якому всі рівні, крім останнього рівня, тобто листкового вузла, повинні бути повністю заповнені, а всі вузли мають бути вирівняні за лівим краєм.
Що таке сортування купи?
Heapsort — популярний і ефективний алгоритм сортування. Концепція сортування купи полягає в тому, щоб вилучати елементи один за одним із частини купи списку, а потім вставляти їх у відсортовану частину списку.
Heapsort — це алгоритм сортування на місці.
основи java
Тепер розглянемо алгоритм сортування купи.
Алгоритм
HeapSort(arr) BuildMaxHeap(arr) for i = length(arr) to 2 swap arr[1] with arr[i] heap_size[arr] = heap_size[arr] ? 1 MaxHeapify(arr,1) End
BuildMaxHeap(arr)
BuildMaxHeap(arr) heap_size(arr) = length(arr) for i = length(arr)/2 to 1 MaxHeapify(arr,i) End
MaxHeapify(arr,i)
MaxHeapify(arr,i) L = left(i) R = right(i) if L ? heap_size[arr] and arr[L] > arr[i] largest = L else largest = i if R ? heap_size[arr] and arr[R] > arr[largest] largest = R if largest != i swap arr[i] with arr[largest] MaxHeapify(arr,largest) End
Робота алгоритму сортування купи
Тепер давайте подивимося, як працює алгоритм Heapsort.
Сортування купи складається з двох етапів сортування елементів. За допомогою алгоритму сортування купи вони такі:
- Перший крок включає створення купи шляхом коригування елементів масиву.
- Після створення купи тепер кілька разів видаліть кореневий елемент купи, перемістивши його в кінець масиву, а потім збережіть структуру купи з рештою елементів.
Тепер давайте детально розглянемо роботу сортування купи на прикладі. Щоб зрозуміти це більш чітко, давайте візьмемо несортований масив і спробуємо відсортувати його за допомогою сортування купи. Це зробить пояснення зрозумілішим і легшим.
По-перше, ми повинні створити купу з заданого масиву та перетворити її на максимальну купу.
Після перетворення даної купи в максимальну купу елементи масиву:
Далі ми повинні видалити кореневий елемент (89) з максимальної купи. Щоб видалити цей вузол, ми повинні поміняти його місцями з останнім вузлом, тобто. (одинадцять). Після видалення кореневого елемента ми знову повинні об’єднати його, щоб перетворити на максимальну купу.
Після заміни елемента масиву 89 з одинадцять, і перетворюючи купу в максимальну купу, елементи масиву -
На наступному кроці нам знову потрібно видалити кореневий елемент (81) з максимальної купи. Щоб видалити цей вузол, ми повинні поміняти його місцями з останнім вузлом, тобто. (54). Після видалення кореневого елемента ми знову повинні об’єднати його, щоб перетворити на максимальну купу.
Після заміни елемента масиву 81 з 54 і перетворюючи купу в максимальну купу, елементи масиву -
На наступному кроці ми повинні видалити кореневий елемент (76) знову з максимальної купи. Щоб видалити цей вузол, ми повинні поміняти його місцями з останнім вузлом, тобто. (9). Після видалення кореневого елемента ми знову повинні об’єднати його, щоб перетворити на максимальну купу.
алфавіт і цифри
Після заміни елемента масиву 76 з 9 і перетворюючи купу в максимальну купу, елементи масиву -
На наступному кроці нам знову потрібно видалити кореневий елемент (54) з максимальної купи. Щоб видалити цей вузол, ми повинні поміняти його місцями з останнім вузлом, тобто. (14). Після видалення кореневого елемента ми знову повинні об’єднати його, щоб перетворити на максимальну купу.
Після заміни елемента масиву 54 з 14 і перетворюючи купу в максимальну купу, елементи масиву -
На наступному кроці нам знову потрібно видалити кореневий елемент (22) з максимальної купи. Щоб видалити цей вузол, ми повинні поміняти його місцями з останнім вузлом, тобто. (одинадцять). Після видалення кореневого елемента ми знову повинні об’єднати його, щоб перетворити на максимальну купу.
Після заміни елемента масиву 22 з одинадцять і перетворюючи купу в максимальну купу, елементи масиву -
На наступному кроці нам знову потрібно видалити кореневий елемент (14) з максимальної купи. Щоб видалити цей вузол, ми повинні поміняти його місцями з останнім вузлом, тобто. (9). Після видалення кореневого елемента ми знову повинні об’єднати його, щоб перетворити на максимальну купу.
Після заміни елемента масиву 14 з 9 і перетворюючи купу в максимальну купу, елементи масиву -
На наступному кроці нам знову потрібно видалити кореневий елемент (одинадцять) з максимальної купи. Щоб видалити цей вузол, ми повинні поміняти його місцями з останнім вузлом, тобто. (9). Після видалення кореневого елемента ми знову повинні об’єднати його, щоб перетворити на максимальну купу.
Після заміни елемента масиву одинадцять з 9, елементи масиву -
Тепер у купі залишився лише один елемент. Після видалення купа буде порожньою.
Після завершення сортування елементи масиву -
Тепер масив повністю відсортований.
Складність сортування купи
Тепер давайте подивимося на часову складність сортування купи в найкращому, середньому та гіршому випадку. Ми також побачимо космічну складність Heapsort.
1. Складність часу
| Справа | Складність часу |
|---|---|
| Кращий випадок | O (n журнал) |
| Середній випадок | O(n log n) |
| Найгірший випадок | O(n log n) |
Часова складність сортування купи становить O (n журнал) у всіх трьох випадках (найкращому випадку, середньому випадку та гіршому випадку). Висота повного бінарного дерева з n елементів дорівнює спокійний.
2. Просторова складність
| Космічна складність | O(1) |
| Стабільний | N0 |
- Просторова складність сортування купи дорівнює O(1).
Реалізація Heapsort
Тепер давайте подивимося на програми Heap сортування на різних мовах програмування.
програма: Напишіть програму для реалізації сортування купи мовою C.
#include /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int arr[], int n) { for (int i = 0; i <n; ++i) { printf('%d', arr[i]); printf(' '); } int main() a[]="{48," 10, 23, 43, 28, 26, 1}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are -
'); printarr(a, n); heapsort(a, printf('
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-20.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C++.</p> <pre> #include using namespace std; /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int a[], int n) { for (int i = 0; i <n; ++i) { cout< <a[i]<<' '; } int main() a[]="{47," 9, 22, 42, 27, 25, 0}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are -
'; printarr(a, n); heapsort(a, cout<<'
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-21.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C#.</p> <pre> using System; class HeapSort { /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ static void heapify(int[] a, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int[] a, int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{46," 8, 21, 41, 26, 24, -1}; int n="a.Length;" console.write('before sorting array elements are -
'); printarr(a, n); heapsort(a, console.write('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-22.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in Java.</p> <pre> class HeapSort { /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ static void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{45," 7, 20, 40, 25, 23, -2}; n="a.length;" system.out.print('before sorting array elements are -
'); printarr(a, n); heapsort(a, system.out.print('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-23.webp" alt="Heap Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>