Řazení haldy je srovnávací technika třídění založená na Binární halda datová struktura. Je to podobné jako u výběr řazení kde nejprve najdeme minimální prvek a umístíme minimální prvek na začátek. Opakujte stejný postup pro zbývající prvky.
Algoritmus řazení haldy
Chcete-li problém vyřešit, postupujte podle níže uvedené myšlenky:
Doporučený problém Nejprve jej prosím vyřešte v PRAXI, než přejdete k řešení Vyřešit problémNejprve převeďte pole do datové struktury haldy pomocí heapify, poté jeden po druhém odstraňte kořenový uzel Max-haldy a nahraďte jej posledním uzlem v haldě a poté navršte kořen haldy. Tento postup opakujte, dokud velikost haldy nebude větší než 1.
osi modelové vrstvy
- Sestavte haldu z daného vstupního pole.
- Opakujte následující kroky, dokud halda nebude obsahovat pouze jeden prvek:
- Zaměňte kořenový prvek hromady (což je největší prvek) s posledním prvkem hromady.
- Odstraňte poslední prvek hromady (který je nyní ve správné poloze).
- Nahromadit zbývající prvky haldy.
- Seřazené pole se získá obrácením pořadí prvků ve vstupním poli.
Detailní zpracování haldy
Abychom lépe porozuměli řazení haldy, vezměme netříděné pole a zkusme ho seřadit pomocí řazení haldy.
Zvažte pole: arr[] = {4, 10, 3, 5, 1}.Sestavení kompletního binárního stromu: Sestavte z pole kompletní binární strom.
Algoritmus řazení haldy | Sestavte kompletní binární strom
Transformace na maximální hromadu: Poté je úkolem sestavit strom z tohoto netříděného pole a pokusit se jej převést na max hromada.
- Chcete-li transformovat haldu na maximální haldu, nadřazený uzel by měl být vždy větší nebo roven podřízeným uzlům.
- Zde, v tomto příkladu, jako nadřazený uzel 4 je menší než podřízený uzel 10, proto je vyměňte za vytvoření maximální haldy.
- Nyní, 4 protože rodič je menší než dítě 5 , tedy oba tyto znovu zaměňte a výsledná halda a pole by měly být takto:
Algoritmus řazení haldy | Max Heapify zkonstruoval binární strom
Proveďte řazení haldy: Odstraňte maximální prvek v každém kroku (tj. přesuňte jej do koncové polohy a odstraňte jej) a poté zvažte zbývající prvky a převeďte je na maximální hromadu.
- Odstraňte kořenový prvek (10) z maximální hromady. Chcete-li tento uzel odstranit, zkuste jej prohodit s posledním uzlem, tj. (1). Po odstranění kořenového prvku jej znovu navršte, abyste jej převedli na maximální haldu.
- Výsledná halda a pole by měly vypadat takto:
Algoritmus řazení haldy | Odstraňte maximum z kořene a maximum heapify
- Opakujte výše uvedené kroky a bude to vypadat následovně:
Algoritmus řazení haldy | Odstraňte další maximum z kořene a max. heapify
- Nyní znovu odstraňte kořen (tj. 3) a proveďte heapify.
Algoritmus řazení haldy | Opakujte předchozí krok
- Nyní, když je kořen znovu odstraněn, je setříděn. a setříděné pole bude podobné arr[] = {1, 3, 4, 5, 10} .
Algoritmus řazení haldy | Konečné seřazené pole
Implementace 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[největší]) největší = l; // Pokud je pravé dítě větší než největší // zatím pokud (r< N && arr[r]>arr[největší]) největší = r; // Pokud největší není kořen if (největší != i) { swap(arr[i], arr[největší]); // Rekurzivně heapify postiženého // podstromu heapify(arr, N, největší); } } // Hlavní funkce pro řazení haldy void heapSort(int arr[], int N) { // Sestavení haldy (přeuspořádání pole) pro (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Postupně extrahuje prvek // z haldy for (int i = N - 1; i> 0; i--) { // Přesune aktuální kořen na konec swap(arr[0], arr[i]); // volání max heapify na zmenšené haldě heapify(arr, i, 0); } } // Obslužná funkce pro tisk pole o velikosti 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[největší]) největší = vlevo; // Pokud je pravé dítě větší než největší // zatím if (vpravo< N && arr[right]>arr[největší]) největší = vpravo; // Prohoďte a pokračujte v heapování // pokud root není největší // Pokud největší není root if (největší != i) { swap(&arr[i], &arr[největší]); // Rekurzivně heapify postiženého // podstromu heapify(arr, N, největší); } } // Hlavní funkce pro řazení haldy void heapSort(int arr[], int N) { // Sestavení maximální haldy pro (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, i); // řazení haldy pro (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]); // Heapify kořenový prvek // pro získání nejvyššího prvku na // root znovu heapify(arr, i, 0); } } // Obslužná funkce pro tisk pole o velikosti 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_.> Jáva // 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); // Postupně extrahuje prvek z haldy for (int i = N - 1; i> 0; i--) { // Přesune aktuální kořen na konec int temp = arr[0]; arr[0] = arr[i]; arr[i] = teplota; // volání max heapify na zmenšené haldě heapify(arr, i, 0); } } // K nahromadění podstromu zakořeněného uzlem i, což je // index v arr[]. n je velikost haldy void heapify(int arr[], int N, int i) { int největší = i; // Inicializuje největší jako kořen int l = 2 * i + 1; // vlevo = 2*i + 1 int r = 2 * i + 2; // vpravo = 2*i + 2 // Pokud je levý potomek větší než kořen, jestliže (l< N && arr[l]>arr[největší]) největší = l; // Pokud je pravé dítě větší než dosud největší, jestliže (r< N && arr[r]>arr[největší]) největší = r; // Pokud největší není kořen if (největší != i) { int swap = arr[i]; arr[i] = arr[největší]; arr[největší] = swap; // Rekurzivně heapify postižený podstrom heapify(arr, N, největší); } } /* Obslužná funkce pro tisk pole o velikosti n */ static void printArray(int arr[]) { int N = arr.length; for (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); // Postupně extrahuje prvek z haldy for (int i = N - 1; i> 0; i--) { // Přesune aktuální kořen na konec int temp = arr[0]; arr[0] = arr[i]; arr[i] = teplota; // volání max heapify na zmenšené haldě heapify(arr, i, 0); } } // K nahromadění podstromu zakořeněného uzlem i, což je // index v arr[]. n je velikost haldy void heapify(int[] arr, int N, int i) { int největší = i; // Inicializuje největší jako kořen int l = 2 * i + 1; // vlevo = 2*i + 1 int r = 2 * i + 2; // vpravo = 2*i + 2 // Pokud je levý potomek větší než kořen, jestliže (l< N && arr[l]>arr[největší]) největší = l; // Pokud je pravé dítě větší než dosud největší, jestliže (r< N && arr[r]>arr[největší]) největší = r; // Pokud největší není kořen if (největší != i) { int swap = arr[i]; arr[i] = arr[největší]; arr[největší] = swap; // Rekurzivně heapify postižený podstrom heapify(arr, N, největší); } } /* Obslužná funkce pro tisk pole o velikosti n */ static void printArray(int[] arr) { int N = arr.Length; for (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); // Postupně extrahuje prvek z haldy for (var i = N - 1; i> 0; i--) { // Přesune aktuální kořen na konec var temp = arr[0]; arr[0] = arr[i]; arr[i] = teplota; // volání max heapify na zmenšené haldě heapify(arr, i, 0); } } // K nahromadění podstromu zakořeněného uzlem i, což je // index v arr[]. n je velikost funkce haldy heapify(arr, N, i) { var největší = i; // Inicializuje největší jako kořen var l = 2 * i + 1; // vlevo = 2*i + 1 var r = 2 * i + 2; // vpravo = 2*i + 2 // Pokud je levý potomek větší než kořen, jestliže (l< N && arr[l]>arr[největší]) největší = l; // Pokud je pravé dítě větší než dosud největší, jestliže (r< N && arr[r]>arr[největší]) největší = r; // Pokud největší není kořen if (největší != i) { var swap = arr[i]; arr[i] = arr[největší]; arr[největší] = swap; // Rekurzivně heapify postižený podstrom heapify(arr, N, největší); } } /* Obslužná funkce pro tisk pole o velikosti n */ function printArray(arr) { var N = arr.length; for (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[$největší]) $největší = $l; // Pokud je pravý potomek větší než dosud největší if ($r< $N && $arr[$r]>$arr[$největší]) $největší = $r; // Pokud největší není root if ($largest != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$největší]; $arr[$největší] = $swap; // Rekurzivně heapify postižený podstrom heapify($arr, $N, $largest); } } // hlavní funkce k provedení funkce řazení haldy heapSort(&$arr, $N) { // Sestavení haldy (přeuspořádání pole) pro ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // Postupně extrahuje prvek z haldy pro ($i = $N-1; $i> 0; $i--) { // Přesune aktuální kořen na konec $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // volání max heapify na zmenšené haldě heapify($arr, $i, 0); } } /* Obslužná funkce pro tisk pole o velikosti n */ funkce 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ýstup
Sorted array is 5 6 7 11 12 13>
Analýza složitosti Řazení haldy
Časová náročnost: O(N log N)
Pomocný prostor: O(log n), kvůli zásobníku rekurzivních volání. Pomocný prostor však může být O(1) pro iterativní implementaci.
Důležité body o třídění haldy:
- Řazení haldy je algoritmus na místě.
- Jeho typická implementace není stabilní, ale může být stabilní (viz tento )
- Typicky 2-3 krát pomalejší než dobře implementované Rychlé třídění . Důvodem pomalosti je nedostatek referenční lokality.
Výhody Heap Sort:
- Efektivní časová náročnost: Heap Sort má ve všech případech časovou složitost O(n log n). Díky tomu je efektivní pro třídění velkých datových sad. The log n faktor pochází z výšky binární haldy a zajišťuje, že algoritmus si zachová dobrý výkon i s velkým počtem prvků.
- Využití paměti - Využití paměti může být minimální (napsáním iterativní heapify() namísto rekurzivní). Takže kromě toho, co je nutné držet počáteční seznam položek, které mají být setříděny, nepotřebuje k práci žádný další paměťový prostor
- jednoduchost - Je snáze pochopitelný než jiné stejně účinné třídicí algoritmy, protože nepoužívá pokročilé koncepty počítačové vědy, jako je rekurze.
Nevýhody Heap Sort:
- Nákladné : Řazení haldy je nákladné, protože konstanty jsou vyšší ve srovnání se slučovacím řazením, i když je časová složitost O(n Log n) u obou.
- Nestabilní : Řazení haldy je nestabilní. Může to změnit relativní pořadí.
- Účinný: Heap Sort není příliš efektivní při práci s vysoce komplexními daty.
Často kladené otázky související s tříděním haldy
Q1. Jaké jsou dvě fáze Heap Sort?
Algoritmus řazení haldy se skládá ze dvou fází. V první fázi se pole převede na maximální haldu. A ve druhé fázi se odstraní nejvyšší prvek (tj. ten v kořeni stromu) a zbývající prvky se použijí k vytvoření nové maximální haldy.
Q2. Proč Heap Sort není stabilní?
Algoritmus řazení haldy není stabilní algoritmus, protože v heapSort() zaměníme arr[i] s arr[0], což může změnit relativní pořadí ekvivalentních klíčů.
Q3. Je Heap Sort příkladem algoritmu Divide and Conquer?
Řazení haldy je NE vůbec algoritmus rozděl a panuj. K efektivnímu třídění prvků používá datovou strukturu haldy, a nikoli přístup rozděl a panuj k třídění prvků.
Q4. Který třídicí algoritmus je lepší – řazení haldy nebo řazení sloučení?
Odpověď spočívá v porovnání jejich časové náročnosti a prostorové náročnosti. Řazení sloučení je o něco rychlejší než řazení halda. Ale na druhou stranu slučovací třídění vyžaduje paměť navíc. V závislosti na požadavcích byste si měli vybrat, který z nich použít.
Q5. Proč je řazení haldy lepší než řazení výběru?
Řazení haldy je podobné třídění výběru, ale s lepším způsobem, jak získat maximum prvku. Využívá datovou strukturu haldy k získání maximálního prvku v konstantním čase