Krūvos rūšiavimas yra palyginimu pagrįsta rūšiavimo technika, pagrįsta Dvejetainė krūva duomenų struktūra. Jis panašus į atrankos rūšiavimas kur pirmiausia randame minimalų elementą ir įdedame minimalų elementą pradžioje. Pakartokite tą patį procesą su likusiais elementais.
Krūvos rūšiavimo algoritmas
Norėdami išspręsti problemą, vadovaukitės toliau pateikta idėja:
Rekomenduojama problema Pirmiausia išspręskite ją praktikoje, prieš pereidami prie problemos sprendimo sprendimoPirmiausia konvertuokite masyvą į krūvos duomenų struktūrą naudodami krūvos formavimą, tada po vieną ištrinkite Max-heap šakninį mazgą ir pakeiskite jį paskutiniu krūvos mazgu, o tada sudėkite krūvos šaknį. Kartokite šį procesą, kol krūvos dydis bus didesnis nei 1.
- Sukurkite krūvą iš pateikto įvesties masyvo.
- Kartokite šiuos veiksmus, kol krūvoje bus tik vienas elementas:
- Sukeiskite šakninį krūvos elementą (kuris yra didžiausias) su paskutiniu krūvos elementu.
- Pašalinkite paskutinį krūvos elementą (kuris dabar yra tinkamoje padėtyje).
- Sudėkite likusius krūvos elementus.
- Surūšiuotas masyvas gaunamas pakeitus elementų tvarką įvesties masyve.
Išsamus krūvos rūšiavimo darbas
Norėdami aiškiau suprasti krūvos rūšiavimą, paimkime nerūšiuotą masyvą ir pabandykite jį surūšiuoti naudodami krūvos rūšiavimą.
Apsvarstykite masyvą: arr [] = {4, 10, 3, 5, 1}.Sukurkite visą dvejetainį medį: Iš masyvo sukurkite pilną dvejetainį medį.
Krūvos rūšiavimo algoritmas | Sukurkite pilną dvejetainį medį
Transformuoti į didžiausią krūvą: Po to užduotis yra sukonstruoti medį iš to nerūšiuoto masyvo ir pabandyti jį konvertuoti į max krūva.
- Norint transformuoti krūvą į didžiausią krūvą, pirminis mazgas visada turi būti didesnis arba lygus antriniams mazgams
- Čia, šiame pavyzdyje, kaip pirminis mazgas 4 yra mažesnis nei antrinis mazgas 10, taigi, sukeiskite juos, kad sukurtumėte didžiausią krūvą.
- Dabar 4 nes tėvas yra mažesnis už vaiką 5 , taigi dar kartą sukeiskite abu, o gauta krūva ir masyvas turėtų būti tokie:
Krūvos rūšiavimo algoritmas | Max Heapify sukonstravo dvejetainį medį
Atlikite krūvos rūšiavimą: Pašalinkite maksimalų elementą kiekviename žingsnyje (t. y. perkelkite jį į galinę padėtį ir pašalinkite), tada apsvarstykite likusius elementus ir paverskite jį maksimalia krūva.
- Ištrinkite šakninį elementą (10) nuo maksimalaus krūvos. Norėdami ištrinti šį mazgą, pabandykite jį sukeisti su paskutiniu mazgu, t.y. (1). Pašalinę šakninį elementą, dar kartą supilkite jį į krūvą, kad konvertuotumėte į maksimalų krūvą.
- Gauta krūva ir masyvas turėtų atrodyti taip:
Krūvos rūšiavimo algoritmas | Pašalinkite maksimumą iš šaknies ir maksimalus sukaupkite
- Pakartokite aukščiau nurodytus veiksmus ir viskas atrodys taip:
Krūvos rūšiavimo algoritmas | Pašalinti kitą maksimumą iš šaknies ir maksimalaus kupono
- Dabar vėl pašalinkite šaknį (t. y. 3) ir atlikite heapify.
Krūvos rūšiavimo algoritmas | Pakartokite ankstesnį veiksmą
- Dabar, kai šaknis dar kartą pašalinama, ji surūšiuojama. ir surūšiuotas masyvas bus panašus arr[] = {1, 3, 4, 5, 10} .
Krūvos rūšiavimo algoritmas | Galutinis surūšiuotas masyvas
Krūvos rūšiavimo įgyvendinimas
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[didžiausias]) didžiausias = l; // Jei dešinysis vaikas didesnis už didžiausią // iki šiol if (r< N && arr[r]>arr[didžiausias]) didžiausias = r; // Jei didžiausias nėra šaknis if (didžiausias != i) { swap(arr[i], arr[didžiausias]); // Rekursyviai didinti paveiktą krūvą // sub-tree heapify(arr, N, didžiausias); } } // Pagrindinė krūvos rūšiavimo funkcija void heapSort(int arr[], int N) { // Sukurti krūvą (pertvarkyti masyvą) (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Po vieną ištraukti elementą // iš krūvos for (int i = N - 1; i> 0; i--) { // Perkelti esamą šaknį į pabaigą swap(arr[0], arr[i]); // iškviesti max heapify sumažintoje krūvoje heapify(arr, i, 0); } } // Naudingumo funkcija spausdinti n dydžio masyvą 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[didžiausias]) didžiausias = kairysis; // Jei dešinysis vaikas didesnis už didžiausią // iki šiol if (dešinėje< N && arr[right]>arr[didžiausias]) didžiausias = dešinysis; // Sukeisti ir tęsti krūvą // jei šaknis nėra didžiausia // Jei didžiausias nėra šaknis if (didžiausias != i) { swap(&arr[i], &arr[didžiausias]); // Rekursyviai didinti paveiktą krūvą // sub-tree heapify(arr, N, didžiausias); } } // Pagrindinė krūvos rūšiavimo funkcija void heapSort(int arr[], int N) { // Sukurti didžiausią krūvą (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, i); // Krūvos rūšiavimas (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]); // Heapify root element // gauti aukščiausią elementą // root again heapify(arr, i, 0); } } // Naudingumo funkcija spausdinti n dydžio masyvą 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); // Po vieną išgauti elementą iš krūvos for (int i = N - 1; i> 0; i--) { // Perkelti dabartinę šaknį į pabaigą int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // iškviesti max heapify sumažintoje krūvoje heapify(arr, i, 0); } } // Pomedžio, kurio šaknys yra mazgas i, kaupimas, kuris yra // indeksas arr[]. n yra krūvos dydis void heapify(int arr[], int N, int i) { int didžiausias = i; // Inicijuoti didžiausią kaip šaknį int l = 2 * i + 1; // kairė = 2*i + 1 int r = 2 * i + 2; // dešinė = 2*i + 2 // Jei kairysis vaikas didesnis už šaknį if (l< N && arr[l]>arr[didžiausias]) didžiausias = l; // Jei dešinysis vaikas yra didesnis nei didžiausias iki šiol if (r< N && arr[r]>arr[didžiausias]) didžiausias = r; // Jei didžiausias nėra šaknis if (didžiausias != i) { int swap = arr[i]; arr[i] = arr[didžiausias]; arr[didžiausias] = apsikeitimas; // Rekursyviai įkrauti paveiktą medį heapify(arr, N, didžiausias); } } /* Naudingumo funkcija, skirta spausdinti n dydžio masyvą */ static void printArray(int arr[]) { int N = arr.length; už (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); // Po vieną išgauti elementą iš krūvos for (int i = N - 1; i> 0; i--) { // Perkelti dabartinę šaknį į pabaigą int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // iškviesti max heapify sumažintoje krūvoje heapify(arr, i, 0); } } // Pomedžio, kurio šaknys yra mazgas i, kaupimas, kuris yra // indeksas arr[]. n yra krūvos dydis void heapify(int[] arr, int N, int i) { int didžiausias = i; // Inicijuoti didžiausią kaip šaknį int l = 2 * i + 1; // kairė = 2*i + 1 int r = 2 * i + 2; // dešinė = 2*i + 2 // Jei kairysis vaikas didesnis už šaknį if (l< N && arr[l]>arr[didžiausias]) didžiausias = l; // Jei dešinysis vaikas yra didesnis nei didžiausias iki šiol if (r< N && arr[r]>arr[didžiausias]) didžiausias = r; // Jei didžiausias nėra šaknis if (didžiausias != i) { int swap = arr[i]; arr[i] = arr[didžiausias]; arr[didžiausias] = apsikeitimas; // Rekursyviai įkrauti paveiktą medį heapify(arr, N, didžiausias); } } /* Naudingumo funkcija, skirta spausdinti n dydžio masyvą */ static void printArray(int[] arr) { int N = arr.Length; už (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); // Vienas po kito ištraukti elementą iš krūvos for (var i = N - 1; i> 0; i--) { // Perkelti dabartinę šaknį į pabaigą var temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // iškviesti max heapify sumažintoje krūvoje heapify(arr, i, 0); } } // Pomedžio, kurio šaknys yra mazgas i, kaupimas, kuris yra // indeksas arr[]. n yra krūvos funkcijos dydis heapify(arr, N, i) { var didžiausias = i; // Inicijuoti didžiausią kaip šaknį var l = 2 * i + 1; // kairė = 2*i + 1 var r = 2 * i + 2; // dešinė = 2*i + 2 // Jei kairysis vaikas didesnis už šaknį if (l< N && arr[l]>arr[didžiausias]) didžiausias = l; // Jei dešinysis vaikas yra didesnis nei didžiausias iki šiol if (r< N && arr[r]>arr[didžiausias]) didžiausias = r; // Jei didžiausias nėra šaknis if (didžiausias != i) { var swap = arr[i]; arr[i] = arr[didžiausias]; arr[didžiausias] = apsikeitimas; // Rekursyviai įkrauti paveiktą medį heapify(arr, N, didžiausias); } } /* Naudingumo funkcija, skirta spausdinti n dydžio masyvą */ funkcija printArray(arr) { var N = arr.length; už (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[$didžiausias]) $didžiausias = $l; // Jei dešinysis vaikas yra didesnis nei didžiausias iki šiol if ($r< $N && $arr[$r]>$arr[$didžiausias]) $didžiausias = $r; // Jei didžiausias nėra šaknis if ($didžiausias != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$didžiausias]; $arr[$didžiausias] = $swap; // Rekursyviai įterpti į krūvą paveikto pomedžio heapify($arr, $N, $largest); } } // pagrindinė funkcija krūvos rūšiavimo funkcijai heapSort(&$arr, $N) { // Sukurti krūvą (pertvarkyti masyvą) ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // Vienas po kito ištraukite elementą iš krūvos ($i = $N-1; $i> 0; $i--) { // Perkelti dabartinę šaknį į pabaigą $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // iškviesti max heapify sumažintoje krūvoje heapify($arr, $i, 0); } } /* Naudingumo funkcija spausdinti n dydžio masyvą */ function 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 Išvestis
Sorted array is 5 6 7 11 12 13>
Sudėtingumo analizė Krūvos rūšiavimas
Laiko sudėtingumas: O (N log N)
Pagalbinė erdvė: O(log n), dėl rekursinio skambučių krūvos. Tačiau iteraciniam įgyvendinimui pagalbinė erdvė gali būti O(1).
Svarbūs punktai apie krūvos rūšiavimą:
- Krūvos rūšiavimas yra algoritmas vietoje.
- Įprastas jo įgyvendinimas nėra stabilus, bet gali būti stabilus (žr tai )
- Paprastai 2–3 kartus lėčiau nei tinkamai įgyvendinta Greitas rūšiavimas . Lėtumo priežastis yra nuorodos vietos trūkumas.
Krūvos rūšiavimo pranašumai:
- Efektyvus laiko sudėtingumas: Visais atvejais krūvos rūšiavimo laiko sudėtingumas yra O(n log n). Tai leidžia efektyviai rūšiuoti didelius duomenų rinkinius. The žurnalo n koeficientas gaunamas iš dvejetainės krūvos aukščio ir užtikrina, kad algoritmas išlaikytų gerą našumą net ir esant dideliam elementų skaičiui.
- Atminties naudojimas - Atminties naudojimas gali būti minimalus (rašant kartotinį heapify() vietoj rekursinio). Taigi, neskaitant to, kas būtina norint turėti pradinį rūšiuojamų elementų sąrašą, jam nereikia papildomos atminties vietos
- Paprastumas - Tai lengviau suprasti nei kiti vienodai veiksmingi rūšiavimo algoritmai, nes jame nenaudojamos pažangios informatikos sąvokos, tokios kaip rekursija.
Krūvos rūšiavimo trūkumai:
- Brangiai kainuoja : Krūvos rūšiavimas yra brangus, nes konstantos yra didesnės, palyginti su sujungimo rūšiavimu, net jei abiejų laiko sudėtingumas yra O(n Log n).
- Nestabilus : krūvos rūšiavimas nestabilus. Tai gali pakeisti santykinę tvarką.
- Efektyvus: Krūvos rūšiavimas nėra labai efektyvus dirbant su labai sudėtingais duomenimis.
Dažnai užduodami klausimai, susiję su krūvos rūšiavimu
Q1. Kokios yra dvi krūvos rūšiavimo fazės?
Krūvos rūšiavimo algoritmas susideda iš dviejų fazių. Pirmajame etape masyvas konvertuojamas į didžiausią krūvą. O antroje fazėje pašalinamas aukščiausias elementas (t.y. esantis prie medžio šaknies), o likę elementai naudojami kuriant naują maksimalų krūvą.
Q2. Kodėl Heap Sort nėra stabilus?
Krūvos rūšiavimo algoritmas nėra stabilus algoritmas, nes mes sukeičiame arr[i] su arr[0] lauke heapSort (), o tai gali pakeisti santykinę lygiaverčių raktų tvarką.
Q3. Ar „Heap Sort“ yra „Skaldyk ir valdyk“ algoritmo pavyzdys?
Krūvos rūšiavimas yra NE iš viso algoritmas „Skaldyk ir valdyk“. Elementams efektyviai rūšiuoti naudojama krūvos duomenų struktūra, o ne elementams rūšiuoti naudojamas „skaldyk ir valdyk“ metodas.
4 klausimas. Kuris rūšiavimo algoritmas geresnis – krūvos rūšiavimas ar sujungimo rūšiavimas?
Atsakymas slypi jų laiko sudėtingumo ir erdvės poreikių palyginime. Rūšiavimas sujungti yra šiek tiek greitesnis nei krūvos rūšiavimas. Tačiau, kita vertus, sujungimas užima papildomos atminties. Priklausomai nuo poreikio, reikėtų pasirinkti, kurį naudoti.
Q5. Kodėl krūvos rūšiavimas yra geresnis nei atrankos rūšiavimas?
Krūvos rūšiavimas yra panašus į pasirinkimo rūšiavimą, bet geresnis būdas gauti maksimalų elementą. Ji naudojasi krūvos duomenų struktūra, kad gautų maksimalų elementą pastoviu laiku
matrica c kalba