В тази статия ще обсъдим алгоритъма за Heapsort. Heap сортирането обработва елементите, като създава min-heap или max-heap, използвайки елементите на дадения масив. Min-heap или max-heap представлява подреждането на масива, в който коренният елемент представлява минималния или максималния елемент на масива.
Сортирането на купчина основно рекурсивно изпълнява две основни операции -
- Изградете куп H, като използвате елементите на масива.
- Многократно изтривайте коренния елемент на купчината, образувана в 1улфаза.
Преди да научим повече за груповото сортиране, нека първо видим кратко описание на Купчина.
Какво е купчина?
Купчината е пълно двоично дърво, а двоичното дърво е дърво, в което възелът може да има най-много две деца. Пълното двоично дърво е двоично дърво, в което всички нива с изключение на последното ниво, т.е. листовия възел, трябва да бъдат напълно запълнени и всички възли трябва да бъдат подравнени вляво.
Какво е групово сортиране?
Heapsort е популярен и ефективен алгоритъм за сортиране. Концепцията за групово сортиране е да елиминирате елементите един по един от купчината на списъка и след това да ги вмъкнете в сортираната част на списъка.
Heapsort е алгоритъмът за сортиране на място.
java regex за
Сега нека видим алгоритъма за сортиране на купчина.
Алгоритъм
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
Работа на алгоритъма за сортиране на Heap
Сега нека видим работата на алгоритъма Heapsort.
При груповото сортиране основно има две фази, включени в сортирането на елементите. С помощта на алгоритъма за сортиране на купчина те са както следва -
- Първата стъпка включва създаването на куп чрез коригиране на елементите на масива.
- След създаването на купчина, сега премахнете коренния елемент на купчината многократно, като го преместите в края на масива, и след това запазете структурата на купчината с останалите елементи.
Сега нека видим работата на heap sort в детайли с помощта на пример. За да го разберем по-ясно, нека вземем несортиран масив и се опитаме да го сортираме с помощта на групово сортиране. Това ще направи обяснението по-ясно и лесно.
Първо, трябва да конструираме купчина от дадения масив и да я преобразуваме в максимална купчина.
След преобразуване на дадения heap в max heap, елементите на масива са -
След това трябва да изтрием основния елемент (89) от максималния куп. За да изтрием този възел, трябва да го разменим с последния възел, т.е. (единадесет). След като изтрием основния елемент, отново трябва да го хейпифицираме, за да го преобразуваме в максимален хейп.
След размяна на елемента на масива 89 с единадесет, и преобразувайки купчината в max-heap, елементите на масива са -
В следващата стъпка отново трябва да изтрием основния елемент (81) от максималния куп. За да изтрием този възел, трябва да го разменим с последния възел, т.е. (54). След като изтрием коренния елемент, отново трябва да го хейпифицираме, за да го преобразуваме в максимален хейп.
След размяна на елемента на масива 81 с 54 и преобразувайки купчината в max-heap, елементите на масива са -
В следващата стъпка трябва да изтрием основния елемент (76) от максималния куп отново. За да изтрием този възел, трябва да го разменим с последния възел, т.е. (9). След като изтрием коренния елемент, отново трябва да го хейпифицираме, за да го преобразуваме в максимален хейп.
След размяна на елемента на масива 76 с 9 и преобразувайки купчината в max-heap, елементите на масива са -
В следващата стъпка отново трябва да изтрием основния елемент (54) от максималния куп. За да изтрием този възел, трябва да го разменим с последния възел, т.е. (14). След като изтрием коренния елемент, отново трябва да го хейпифицираме, за да го преобразуваме в максимален хейп.
След размяна на елемента на масива 54 с 14 и преобразувайки купчината в max-heap, елементите на масива са -
В следващата стъпка отново трябва да изтрием основния елемент (22) от максималния куп. За да изтрием този възел, трябва да го разменим с последния възел, т.е. (единадесет). След като изтрием коренния елемент, отново трябва да го хейпифицираме, за да го преобразуваме в максимален хейп.
След размяна на елемента на масива 22 с единадесет и преобразувайки купчината в max-heap, елементите на масива са -
В следващата стъпка отново трябва да изтрием основния елемент (14) от максималния куп. За да изтрием този възел, трябва да го разменим с последния възел, т.е. (9). След като изтрием коренния елемент, отново трябва да го хейпифицираме, за да го преобразуваме в максимален хейп.
След размяна на елемента на масива 14 с 9 и преобразувайки купчината в max-heap, елементите на масива са -
В следващата стъпка отново трябва да изтрием основния елемент (единадесет) от максималния куп. За да изтрием този възел, трябва да го разменим с последния възел, т.е. (9). След като изтрием коренния елемент, отново трябва да го хейпифицираме, за да го преобразуваме в максимален хейп.
След размяна на елемента на масива единадесет с 9, елементите на масива са -
Сега купчината има само един останал елемент. След като го изтриете, купчината ще бъде празна.
След завършване на сортирането, елементите на масива са -
Сега масивът е напълно сортиран.
numpy точков продукт
Сложност на сортиране на купчина
Сега нека видим времевата сложност на Heap sort в най-добрия случай, средния случай и най-лошия случай. Ще видим и космическата сложност на Heapsort.
1. Времева сложност
| Случай | Времева сложност |
|---|---|
| Най-добър случай | O (n журнал) |
| Среден случай | O(n log n) |
| Най-лошия случай | O(n log n) |
Времевата сложност на сортирането на купчина е O (n журнал) и в трите случая (най-добър случай, среден случай и най-лош случай). Височината на пълно двоично дърво с n елемента е спокоен.
2. Космическа сложност
| Космическа сложност | О(1) |
| Стабилен | N0 |
- Пространствената сложност на Heap sort е O(1).
Внедряване на Heapsort
Сега, нека видим програмите на Heap sort в различни езици за програмиране.
програма: Напишете програма за реализиране на сортиране на купчина на език 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;>