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 1^svfá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ť

Najlepšia zložitosť prípadu -Vyskytuje sa, keď nie je potrebné žiadne triedenie, t. j. pole je už zoradené. Najlepšia časová zložitosť triedenia haldy je O(n log). Priemerná zložitosť prípadu -Vyskytuje sa vtedy, keď sú prvky poľa v premiešanom poradí, ktoré nie je správne vzostupné a nesprávne zostupné. Priemerná časová zložitosť triedenia haldy je O(n log n). Zložitosť najhoršieho prípadu -Vyskytuje sa, keď sa vyžaduje, aby boli prvky poľa zoradené v opačnom poradí. To znamená, že musíte zoradiť prvky poľa vo vzostupnom poradí, ale jeho prvky sú v zostupnom poradí. Najhorším prípadom je časová zložitosť triedenia haldy 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ť 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 &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; 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 &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 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 &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; 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 &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 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 &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; 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 &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 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 &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; 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 &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 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&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>