V tomto článku budeme diskutovat o algoritmu Heapsort. Řazení haldy zpracuje prvky tak, že vytvoří min-heap nebo max-heap pomocí prvků daného pole. Min-heap nebo max-heap představuje uspořádání pole, ve kterém kořenový prvek představuje minimální nebo maximální prvek pole.
Řazení haldy v podstatě rekurzivně provádí dvě hlavní operace -
- Sestavte haldu H pomocí prvků pole.
- Opakovaně odstraňte kořenový prvek haldy vytvořené v 1Svatýfáze.
Než se dozvíme více o třídění haldy, podívejme se nejprve na stručný popis Halda.
Co je to hromada?
Halda je úplný binární strom a binární strom je strom, ve kterém může mít uzel maximálně dva potomky. Úplný binární strom je binární strom, ve kterém by všechny úrovně kromě poslední úrovně, tj. listového uzlu, měly být zcela vyplněny a všechny uzly by měly být zarovnány doleva.
Co je haldové řazení?
Heapsort je populární a efektivní třídicí algoritmus. Koncept řazení haldy je odstranit prvky jeden po druhém z části haldy seznamu a poté je vložit do seřazené části seznamu.
Heapsort je místní třídicí algoritmus.
Herec Rekha
Nyní se podívejme na algoritmus řazení haldy.
Algoritmus
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
Fungování algoritmu řazení haldy
Nyní se podívejme, jak funguje Heapsort Algorithm.
Při třídění haldy v zásadě existují dvě fáze, které se účastní třídění prvků. Při použití algoritmu řazení haldy jsou následující -
- První krok zahrnuje vytvoření haldy úpravou prvků pole.
- Po vytvoření haldy nyní odeberte kořenový prvek haldy opakovaně tak, že jej posunete na konec pole, a poté uložte strukturu haldy se zbývajícími elementy.
Nyní se podívejme na fungování třídění haldy podrobně na příkladu. Abychom tomu porozuměli jasněji, vezměme nesetříděné pole a zkusme ho seřadit pomocí řazení haldy. Vysvětlování bude jasnější a jednodušší.
Nejprve musíme z daného pole sestavit haldu a převést ji na maximální haldu.
Po převedení dané haldy na maximální haldu jsou prvky pole -
Dále musíme odstranit kořenový prvek (89) z maximální hromady. Abychom tento uzel smazali, musíme jej prohodit s posledním uzlem, tzn. (jedenáct). Po smazání kořenového prvku jej musíme znovu nahromadit, abychom jej převedli na maximální haldu.
Po výměně prvku pole 89 s jedenáct, a převedením haldy na maximální haldu jsou prvky pole -
V dalším kroku opět musíme odstranit kořenový prvek (81) z maximální hromady. Abychom tento uzel smazali, musíme jej prohodit s posledním uzlem, tzn. (54). Po smazání kořenového prvku jej musíme znovu nahromadit, abychom jej převedli na maximální haldu.
Po výměně prvku pole 81 s 54 a převedením haldy na maximální haldu jsou prvky pole -
V dalším kroku musíme odstranit kořenový prvek (76) opět z maximální hromady. Abychom tento uzel smazali, musíme jej prohodit s posledním uzlem, tzn. (9). Po smazání kořenového prvku jej musíme znovu nahromadit, abychom jej převedli na maximální haldu.
Po výměně prvku pole 76 s 9 a převedením haldy na maximální haldu jsou prvky pole -
V dalším kroku opět musíme odstranit kořenový prvek (54) z maximální hromady. Abychom tento uzel smazali, musíme jej prohodit s posledním uzlem, tzn. (14). Po smazání kořenového prvku jej musíme znovu nahromadit, abychom jej převedli na maximální haldu.
spát v js
Po výměně prvku pole 54 s 14 a převedením haldy na maximální haldu jsou prvky pole -
V dalším kroku opět musíme odstranit kořenový prvek (22) z maximální hromady. Abychom tento uzel smazali, musíme jej prohodit s posledním uzlem, tzn. (jedenáct). Po smazání kořenového prvku jej musíme znovu nahromadit, abychom jej převedli na maximální haldu.
Po výměně prvku pole 22 s jedenáct a převedením haldy na maximální haldu jsou prvky pole -
V dalším kroku opět musíme odstranit kořenový prvek (14) z maximální hromady. Abychom tento uzel smazali, musíme jej prohodit s posledním uzlem, tzn. (9). Po smazání kořenového prvku jej musíme znovu nahromadit, abychom jej převedli na maximální haldu.
Po výměně prvku pole 14 s 9 a převedením haldy na maximální haldu jsou prvky pole -
V dalším kroku opět musíme odstranit kořenový prvek (jedenáct) z maximální hromady. Abychom tento uzel smazali, musíme jej prohodit s posledním uzlem, tzn. (9). Po smazání kořenového prvku jej musíme znovu nahromadit, abychom jej převedli na maximální haldu.
Po výměně prvku pole jedenáct s 9, prvky pole jsou -
Nyní hromadě zbývá pouze jeden prvek. Po smazání bude halda prázdná.
Po dokončení řazení jsou prvky pole -
Nyní je pole kompletně seřazeno.
Složitost řazení haldy
Nyní se podívejme na časovou složitost řazení Heap v nejlepším případě, průměrném případě a nejhorším případě. Uvidíme také vesmírnou složitost Heapsortu.
1. Časová složitost
| Pouzdro | Časová složitost |
|---|---|
| Nejlepší případ | O(n log) |
| Průměrný případ | O(n log n) |
| Nejhorší případ | O(n log n) |
Časová složitost řazení haldy je O(n log) ve všech třech případech (nejlepší případ, průměrný případ a nejhorší případ). Výška úplného binárního stromu s n prvky je uklidnit.
2. Prostorová složitost
| Vesmírná složitost | O(1) |
| Stabilní | N0 |
- Prostorová složitost řazení haldy je O(1).
Implementace Heapsort
Nyní se podívejme na programy řazení Heap v různých programovacích jazycích.
Program: Napište program pro implementaci řazení haldy v jazyce 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;>