V tomto článku budeme diskutovať o algoritme Heapsort. Zoradenie haldy spracuje prvky vytvorením minimálnej haldy alebo maximálnej haldy pomocou prvkov daného poľa. Min-heap alebo max-heap predstavuje poradie poľa, v ktorom koreňový prvok predstavuje minimálny alebo maximálny prvok poľa.
Zoradenie haldy v podstate rekurzívne vykonáva dve hlavné operácie -
- Zostavte haldu H pomocou prvkov poľa.
- Opakovane odstráňte koreňový prvok haldy vytvorenej v 1svfáza.
Predtým, ako sa dozvieme viac o triedení haldy, pozrime sa najprv na stručný popis Hromada.
čo je to halda?
Halda je úplný binárny strom a binárny strom je strom, v ktorom môže mať uzol maximálne dve deti. Úplný binárny strom je binárny strom, v ktorom by mali byť všetky úrovne okrem poslednej úrovne, t. j. listového uzla, úplne vyplnené a všetky uzly by mali byť zarovnané doľava.
Čo je haldové triedenie?
Heapsort je populárny a efektívny triediaci algoritmus. Koncept zoradenia haldy je odstrániť prvky jeden po druhom z časti haldy zoznamu a potom ich vložiť do zoradenej časti zoznamu.
Heapsort je algoritmus triedenia na mieste.
python nový riadok
Teraz sa pozrime na algoritmus triedenia 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
Fungovanie algoritmu triedenia haldy
Teraz sa pozrime na fungovanie Heapsort Algorithmu.
Pri triedení haldy v zásade existujú dve fázy zapojené do triedenia prvkov. Použitím algoritmu triedenia haldy sú tieto -
- Prvý krok zahŕňa vytvorenie haldy úpravou prvkov poľa.
- Po vytvorení haldy teraz opakovane odstráňte koreňový prvok haldy posunutím na koniec poľa a potom uložte štruktúru haldy so zostávajúcimi elementmi.
Teraz sa pozrime na fungovanie triedenia haldy podrobne pomocou príkladu. Aby sme to pochopili jasnejšie, zoberme si nezoradené pole a skúsme ho zoradiť pomocou triedenia haldy. Vysvetlenie bude jasnejšie a jednoduchšie.
Najprv musíme z daného poľa zostaviť haldu a previesť ju na maximálnu haldu.
Po konverzii danej haldy na maximálnu haldu sú prvky poľa -
Ďalej musíme odstrániť koreňový prvok (89) z maximálnej hromady. Aby sme tento uzol vymazali, musíme ho prehodiť s posledným uzlom, t.j. (jedenásť). Po odstránení koreňového prvku ho musíme opäť nahromadiť, aby sme ho premenili na maximálnu haldu.
Po výmene prvku poľa 89 s jedenásť, a pri konverzii haldy na maximálnu haldu sú prvky poľa -
V ďalšom kroku opäť musíme odstrániť koreňový prvok (81) z maximálnej hromady. Aby sme tento uzol vymazali, musíme ho prehodiť s posledným uzlom, t.j. (54). Po odstránení koreňového prvku ho musíme opäť nahromadiť, aby sme ho premenili na maximálnu haldu.
Po výmene prvku poľa 81 s 54 a pri konverzii haldy na maximálnu haldu sú prvky poľa -
V ďalšom kroku musíme odstrániť koreňový prvok (76) opäť z maximálnej haldy. Aby sme tento uzol vymazali, musíme ho prehodiť s posledným uzlom, t.j. (9). Po odstránení koreňového prvku ho musíme opäť nahromadiť, aby sme ho premenili na maximálnu haldu.
Po výmene prvku poľa 76 s 9 a pri konverzii haldy na maximálnu haldu sú prvky poľa -
V ďalšom kroku opäť musíme odstrániť koreňový prvok (54) z maximálnej hromady. Aby sme tento uzol vymazali, musíme ho prehodiť s posledným uzlom, t.j. (14). Po odstránení koreňového prvku ho musíme opäť nahromadiť, aby sme ho premenili na maximálnu haldu.
Po výmene prvku poľa 54 s 14 a pri konverzii haldy na maximálnu haldu sú prvky poľa -
V ďalšom kroku opäť musíme odstrániť koreňový prvok (22) z maximálnej hromady. Aby sme tento uzol vymazali, musíme ho prehodiť s posledným uzlom, t.j. (jedenásť). Po odstránení koreňového prvku ho musíme opäť nahromadiť, aby sme ho premenili na maximálnu haldu.
Po výmene prvku poľa 22 s jedenásť a pri konverzii haldy na maximálnu haldu sú prvky poľa -
V ďalšom kroku opäť musíme odstrániť koreňový prvok (14) z maximálnej hromady. Aby sme tento uzol vymazali, musíme ho prehodiť s posledným uzlom, t.j. (9). Po odstránení koreňového prvku ho musíme opäť nahromadiť, aby sme ho premenili na maximálnu haldu.
Po výmene prvku poľa 14 s 9 a pri konverzii haldy na maximálnu haldu sú prvky poľa -
V ďalšom kroku opäť musíme odstrániť koreňový prvok (jedenásť) z maximálnej hromady. Aby sme tento uzol vymazali, musíme ho prehodiť s posledným uzlom, t.j. (9). Po odstránení koreňového prvku ho musíme opäť nahromadiť, aby sme ho premenili na maximálnu haldu.
Po výmene prvku poľa jedenásť s 9, prvky poľa sú -
obojsmerné plánovanie
Teraz hromade zostal iba jeden prvok. Po jeho odstránení bude halda prázdna.
Po dokončení triedenia sú prvky poľa -
Teraz je pole úplne zoradené.
Zložitosť triedenia haldy
Teraz sa pozrime na časovú zložitosť triedenia Heap v najlepšom prípade, priemernom prípade a najhoršom prípade. Uvidíme aj vesmírnu zložitosť Heapsortu.
1. Časová zložitosť
| Prípad | Časová zložitosť |
|---|---|
| Najlepší prípad | O (n denník) |
| Priemerný prípad | O(n log n) |
| V najhoršom prípade | O(n log n) |
Časová zložitosť triedenia haldy je O (n denník) vo všetkých troch prípadoch (najlepší prípad, priemerný prípad a najhorší prípad). Výška úplného binárneho stromu s n prvkami je pokojne.
2. Zložitosť priestoru
| Priestorová zložitosť | O(1) |
| Stabilný | N0 |
- Priestorová zložitosť triedenia haldy je O(1).
Implementácia Heapsort
Teraz sa pozrime na programy triedenia Heap v rôznych programovacích jazykoch.
Program: Napíšte program na implementáciu triedenia haldy v jazyku 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;>