Triediť haldy je porovnávacia technika triedenia založená na Binárna halda dátová štruktúra. Je to podobné ako triedenie výberu kde najskôr nájdeme minimálny prvok a umiestnime minimálny prvok na začiatok. Opakujte rovnaký postup pre zostávajúce prvky.
Algoritmus triedenia haldy
Ak chcete problém vyriešiť, postupujte podľa nasledujúcej myšlienky:
css zalomenie textu
Odporúčaný problém Najskôr ho vyriešte v PRAXI, až potom prejdite na riešenie Vyriešiť problémNajprv skonvertujte pole na dátovú štruktúru haldy pomocou heapify, potom jeden po druhom odstráňte koreňový uzol haldy Max a nahraďte ho posledným uzlom haldy a potom nahromadte koreň haldy. Tento postup opakujte, kým veľkosť haldy nebude väčšia ako 1.
- Zostavte haldu z daného vstupného poľa.
- Opakujte nasledujúce kroky, kým halda nebude obsahovať iba jeden prvok:
- Vymeňte koreňový prvok haldy (ktorý je najväčším prvkom) s posledným prvkom haldy.
- Odstráňte posledný prvok haldy (ktorý je teraz v správnej polohe).
- Zostávajúce prvky haldy nahromadiť.
- Zoradené pole sa získa obrátením poradia prvkov vo vstupnom poli.
Detailné spracovanie haldy
Aby sme jasnejšie pochopili triedenie haldy, zoberme si netriedené pole a skúsme ho zoradiť pomocou triedenia haldy.
Zvážte pole: arr[] = {4, 10, 3, 5, 1}.Zostavte kompletný binárny strom: Zostavte kompletný binárny strom z poľa.
Algoritmus triedenia haldy | Zostavte kompletný binárny strom
Transformácia na maximálnu hromadu: Potom je úlohou vytvoriť strom z tohto netriedeného poľa a pokúsiť sa ho previesť na max hromada.
- Ak chcete transformovať haldu na maximálnu haldu, nadradený uzol by mal byť vždy väčší alebo rovnaký ako podriadené uzly
- Tu, v tomto príklade, ako nadradený uzol 4 je menší ako podradený uzol 10, preto ich vymeňte za vytvorenie maximálnej haldy.
- teraz 4 ako rodič je menší ako dieťa 5 , teda obe tieto znova zameňte a výsledná halda a pole by mali byť takéto:
Algoritmus triedenia haldy | Max Heapify vytvoril binárny strom
Vykonajte triedenie haldy: Odstráňte maximálny prvok v každom kroku (t. j. presuňte ho do koncovej polohy a odstráňte ho) a potom zvážte zostávajúce prvky a premeňte ho na maximálnu hromadu.
- Odstráňte koreňový prvok (10) z maximálnej hromady. Aby ste tento uzol vymazali, skúste ho vymeniť s posledným uzlom, t.j. (1). Po odstránení koreňového prvku ho znova navŕšte, aby ste ho premenili na maximálnu hromadu.
- Výsledná halda a pole by mali vyzerať takto:
Algoritmus triedenia haldy | Odstrániť maximum z root a max heapify
shweta tiwari
- Opakujte vyššie uvedené kroky a bude to vyzerať takto:
Algoritmus triedenia haldy | Odstráňte ďalšie maximum z root a max heapify
- Teraz znova odstráňte koreň (t.j. 3) a vykonajte heapify.
Algoritmus triedenia haldy | Opakujte predchádzajúci krok
- Teraz, keď je koreň znova odstránený, je triedený. a zoradené pole bude podobné arr[] = {1, 3, 4, 5, 10} .
Algoritmus triedenia haldy | Konečné zoradené pole
Implementácia Heap Sort
C++ // C++ program for implementation of Heap Sort #include using namespace std; // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) { // Initialize largest as root int largest = i; // left = 2*i + 1 int l = 2 * i + 1; // right = 2*i + 2 int r = 2 * i + 2; // If left child is larger than root if (l < N && arr[l]>arr[najväčší]) najväčší = l; // Ak je pravé dieťa väčšie ako najväčšie // zatiaľ ak (r< N && arr[r]>arr[najväčší]) najväčší = r; // Ak najväčší nie je koreň if (najväčší != i) { swap(arr[i], arr[najväčší]); // Rekurzívne nahromadiť postihnutý // podstrom heapify(arr, N, najväčší); } } // Hlavná funkcia na triedenie haldy void heapSort(int arr[], int N) { // Vytvorenie haldy (zmena usporiadania poľa) pre (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Postupne extrahujte prvok // z haldy for (int i = N - 1; i> 0; i--) { // Presuňte aktuálny koreň na koniec swap(arr[0], arr[i]); // volanie max heapify na zmenšenej halde heapify(arr, i, 0); } } // Pomocná funkcia na tlač poľa veľkosti n void printArray(int arr[], int N) { for (int i = 0; i< N; ++i) cout << arr[i] << ' '; cout << '
'; } // Driver's code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call heapSort(arr, N); cout << 'Sorted array is
'; printArray(arr, N); }> C // Heap Sort in C #include // Function to swap the position of two elements void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // To heapify a subtree rooted with node i // which is an index in arr[]. // n is size of heap void heapify(int arr[], int N, int i) { // Find largest among root, // left child and right child // Initialize largest as root int largest = i; // left = 2*i + 1 int left = 2 * i + 1; // right = 2*i + 2 int right = 2 * i + 2; // If left child is larger than root if (left < N && arr[left]>arr[najväčší]) najväčší = vľavo; // Ak je pravé dieťa väčšie ako najväčšie // zatiaľ ak (vpravo< N && arr[right]>arr[najväčší]) najväčší = pravý; // Vymeňte a pokračujte v heapovaní // ak root nie je najväčší // Ak najväčší nie je root if (najväčší != i) { swap(&arr[i], &arr[najväčší]); // Rekurzívne nahromadiť postihnutý // podstrom heapify(arr, N, najväčší); } } // Hlavná funkcia na triedenie haldy void heapSort(int arr[], int N) { // Vytvorenie maximálnej haldy pre (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, i); // Zoradenie haldy pre (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]); // Heapify koreňový prvok // na získanie najvyššieho prvku na // root znovu heapify(arr, i, 0); } } // Pomocná funkcia na tlač poľa veľkosti n void printArray(int arr[], int N) { for (int i = 0; i< N; i++) printf('%d ', arr[i]); printf('
'); } // Driver's code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call heapSort(arr, N); printf('Sorted array is
'); printArray(arr, N); } // This code is contributed by _i_plus_plus_.> Java // Java program for implementation of Heap Sort public class HeapSort { public void sort(int arr[]) { int N = arr.length; // Build heap (rearrange array) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Postupne extrahuje prvok z haldy for (int i = N - 1; i> 0; i--) { // Presunie aktuálny koreň na koniec int temp = arr[0]; arr[0] = arr[i]; arr[i] = teplota; // volanie max heapify na zmenšenej halde heapify(arr, i, 0); } } // Na vytvorenie podstromu zakoreneného uzlom i, ktorý je // indexom v arr[]. n je veľkosť haldy void heapify(int arr[], int N, int i) { int najväčšia = i; // Inicializuje najväčší ako koreň int l = 2 * i + 1; // vľavo = 2*i + 1 int r = 2 * i + 2; // vpravo = 2*i + 2 // Ak je ľavé dieťa väčšie ako koreň, ak (l< N && arr[l]>arr[najväčší]) najväčší = l; // Ak je pravé dieťa väčšie ako doteraz najväčšie, ak (r< N && arr[r]>arr[najväčší]) najväčší = r; // Ak najväčší nie je koreň if (najväčší != i) { int swap = arr[i]; arr[i] = arr[najväčší]; arr[najväčší] = swap; // Rekurzívne heapify postihnutý podstrom heapify(arr, N, najväčší); } } /* Pomocná funkcia na tlač poľa veľkosti n */ static void printArray(int arr[]) { int N = arr.length; pre (int i = 0; i< N; ++i) System.out.print(arr[i] + ' '); System.out.println(); } // Driver's code public static void main(String args[]) { int arr[] = { 12, 11, 13, 5, 6, 7 }; int N = arr.length; // Function call HeapSort ob = new HeapSort(); ob.sort(arr); System.out.println('Sorted array is'); printArray(arr); } }> C# // C# program for implementation of Heap Sort using System; public class HeapSort { public void sort(int[] arr) { int N = arr.Length; // Build heap (rearrange array) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Postupne extrahuje prvok z haldy for (int i = N - 1; i> 0; i--) { // Presunie aktuálny koreň na koniec int temp = arr[0]; arr[0] = arr[i]; arr[i] = teplota; // volanie max heapify na zmenšenej halde heapify(arr, i, 0); } } // Na vytvorenie podstromu zakoreneného uzlom i, ktorý je // indexom v arr[]. n je veľkosť haldy void heapify(int[] arr, int N, int i) { int najväčšia = i; // Inicializuje najväčší ako koreň int l = 2 * i + 1; // vľavo = 2*i + 1 int r = 2 * i + 2; // vpravo = 2*i + 2 // Ak je ľavé dieťa väčšie ako koreň, ak (l< N && arr[l]>arr[najväčší]) najväčší = l; // Ak je pravé dieťa väčšie ako doteraz najväčšie, ak (r< N && arr[r]>arr[najväčší]) najväčší = r; // Ak najväčší nie je koreň if (najväčší != i) { int swap = arr[i]; arr[i] = arr[najväčší]; arr[najväčší] = swap; // Rekurzívne heapify postihnutý podstrom heapify(arr, N, najväčší); } } /* Pomocná funkcia na tlač poľa veľkosti n */ static void printArray(int[] arr) { int N = arr.Length; pre (int i = 0; i< N; ++i) Console.Write(arr[i] + ' '); Console.Read(); } // Driver's code public static void Main() { int[] arr = { 12, 11, 13, 5, 6, 7 }; int N = arr.Length; // Function call HeapSort ob = new HeapSort(); ob.sort(arr); Console.WriteLine('Sorted array is'); printArray(arr); } } // This code is contributed // by Akanksha Rai(Abby_akku)> Javascript // JavaScript program for implementation // of Heap Sort function sort( arr) { var N = arr.length; // Build heap (rearrange array) for (var i = Math.floor(N / 2) - 1; i>= 0; i--) heapify(arr, N, i); // Postupne extrahuje prvok z haldy for (var i = N - 1; i> 0; i--) { // Presunie aktuálny koreň na koniec var temp = arr[0]; arr[0] = arr[i]; arr[i] = teplota; // volanie max heapify na zmenšenej halde heapify(arr, i, 0); } } // Na vytvorenie podstromu zakoreneného uzlom i, ktorý je // indexom v arr[]. n je veľkosť funkcie haldy heapify(arr, N, i) { var najväčšia = i; // Inicializácia najväčšieho ako koreň var l = 2 * i + 1; // vľavo = 2*i + 1 var r = 2 * i + 2; // vpravo = 2*i + 2 // Ak je ľavé dieťa väčšie ako koreň, ak (l< N && arr[l]>arr[najväčší]) najväčší = l; // Ak je pravé dieťa väčšie ako doteraz najväčšie, ak (r< N && arr[r]>arr[najväčší]) najväčší = r; // Ak najväčší nie je koreň if (najväčší != i) { var swap = arr[i]; arr[i] = arr[najväčší]; arr[najväčší] = swap; // Rekurzívne heapify postihnutý podstrom heapify(arr, N, najväčší); } } /* Pomocná funkcia na tlač poľa veľkosti n */ function printArray(arr) { var N = arr.length; pre (var i = 0; i< N; ++i) document.write(arr[i] + ' '); } var arr = [12, 11, 13, 5, 6, 7]; var N = arr.length; sort(arr); document.write( 'Sorted array is'); printArray(arr, N); // This code is contributed by SoumikMondal> PHP // Php program for implementation of Heap Sort // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap function heapify(&$arr, $N, $i) { $largest = $i; // Initialize largest as root $l = 2*$i + 1; // left = 2*i + 1 $r = 2*$i + 2; // right = 2*i + 2 // If left child is larger than root if ($l < $N && $arr[$l]>$arr[$najväčší]) $najväčší = $l; // Ak je pravé dieťa väčšie ako doteraz najväčšie if ($r< $N && $arr[$r]>$arr[$najväčší]) $najväčší = $r; // Ak najväčší nie je root if ($najväčší != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$najväčší]; $arr[$najvacsi] = $swap; // Rekurzívne heapify postihnutý podstrom heapify($arr, $N, $najväčší); } } // hlavná funkcia na vykonanie funkcie triedenia haldy heapSort(&$arr, $N) { // Vytvorenie haldy (zmena usporiadania poľa) pre ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // Postupne extrahuje prvok z haldy pre ($i = $N-1; $i> 0; $i--) { // Presunie aktuálny koreň na koniec $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // volanie max heapify na zmenšenej halde heapify($arr, $i, 0); } } /* Pomocná funkcia na tlač poľa veľkosti n */ funkcia printArray(&$arr, $N) { for ($i = 0; $i< $N; ++$i) echo ($arr[$i].' ') ; } // Driver's program $arr = array(12, 11, 13, 5, 6, 7); $N = sizeof($arr)/sizeof($arr[0]); // Function call heapSort($arr, $N); echo 'Sorted array is ' . '
'; printArray($arr , $N); // This code is contributed by Shivi_Aggarwal ?>> Python3 # Python program for implementation of heap Sort # To heapify subtree rooted at index i. # n is size of heap def heapify(arr, N, i): largest = i # Initialize largest as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 # See if left child of root exists and is # greater than root if l < N and arr[largest] < arr[l]: largest = l # See if right child of root exists and is # greater than root if r < N and arr[largest] < arr[r]: largest = r # Change root, if needed if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # swap # Heapify the root. heapify(arr, N, largest) # The main function to sort an array of given size def heapSort(arr): N = len(arr) # Build a maxheap. for i in range(N//2 - 1, -1, -1): heapify(arr, N, i) # One by one extract elements for i in range(N-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # swap heapify(arr, i, 0) # Driver's code if __name__ == '__main__': arr = [12, 11, 13, 5, 6, 7] # Function call heapSort(arr) N = len(arr) print('Sorted array is') for i in range(N): print('%d' % arr[i], end=' ') # This code is contributed by Mohit Kumra> Výkon
Sorted array is 5 6 7 11 12 13>
Analýza zložitosti Hromadné triedenie
Časová zložitosť: O(N log N)
Pomocný priestor: O(log n) v dôsledku zásobníka rekurzívnych hovorov. Pomocný priestor však môže byť O(1) pre iteratívnu implementáciu.
Dôležité body o triedení hromady:
- Zoradenie haldy je algoritmus na mieste.
- Jeho typická implementácia nie je stabilná, ale môže byť stabilná (pozri toto )
- Typicky 2-3 krát pomalšie ako dobre implementované QuickSort . Dôvodom pomalosti je nedostatok referenčnej lokality.
Výhody triedenia haldy:
- Efektívna časová zložitosť: Heap Sort má vo všetkých prípadoch časovú zložitosť O(n log n). Vďaka tomu je efektívne pri triedení veľkých súborov údajov. The log n faktor vychádza z výšky binárnej haldy a zabezpečuje, že algoritmus si udrží dobrý výkon aj pri veľkom počte prvkov.
- Využitie pamäte - Využitie pamäte môže byť minimálne (napísaním iteratívneho heapify() namiesto rekurzívneho). Takže okrem toho, čo je potrebné držať počiatočný zoznam položiek, ktoré sa majú triediť, nepotrebuje na prácu žiadny ďalší pamäťový priestor
- jednoduchosť - Je jednoduchšie pochopiť ako iné rovnako efektívne triediace algoritmy, pretože nepoužíva pokročilé koncepty informatiky, ako je rekurzia.
Nevýhody triedenia haldy:
- Nákladné : Haldové triedenie je nákladné, pretože konštanty sú vyššie v porovnaní so zlučovacím triedením, aj keď je časová zložitosť O(n Log n) pre obe.
- Nestabilný : Zoradenie haldy je nestabilné. Môže to zmeniť usporiadanie relatívneho poradia.
- Efektívne: Heap Sort nie je veľmi efektívny pri práci s veľmi zložitými dátami.
Často kladené otázky súvisiace s triedením haldy
Q1. Aké sú dve fázy Heap Sort?
Algoritmus triedenia haldy pozostáva z dvoch fáz. V prvej fáze sa pole prevedie na maximálnu haldu. A v druhej fáze sa odstráni najvyšší prvok (t. j. ten v koreni stromu) a zvyšné prvky sa použijú na vytvorenie novej maximálnej haldy.
Q2. Prečo Heap Sort nie je stabilný?
Algoritmus triedenia haldy nie je stabilný algoritmus, pretože v heapSort() zamieňame arr[i] s arr[0], čo môže zmeniť relatívne poradie ekvivalentných kľúčov.
Q3. Je Heap Sort príkladom algoritmu Divide and Conquer?
rímske číslice 1 100
Triedenie haldy je NIE vôbec algoritmus rozdeľuj a panuj. Používa haldovú dátovú štruktúru na efektívne triedenie svojich prvkov a nie prístup rozdeľuj a panuj na triedenie prvkov.
Q4. Ktorý triediaci algoritmus je lepší – triedenie haldy alebo triedenie zlúčenia?
Odpoveď spočíva v porovnaní ich časovej náročnosti a priestorových nárokov. Zoradenie zlúčiť je o niečo rýchlejšie ako zoradenie haldy. Ale na druhej strane zlučovacie triedenie vyžaduje dodatočnú pamäť. V závislosti od požiadavky by ste si mali vybrať, ktorý z nich použijete.
Q5. Prečo je triedenie haldy lepšie ako triedenie výberu?
Zoradenie haldy je podobné triedeniu výberu, ale s lepším spôsobom, ako získať maximálny prvok. Využíva štruktúru údajov haldy na získanie maximálneho prvku v konštantnom čase