Razvrščanje kopice je tehnika razvrščanja, ki temelji na primerjavi Binarna kopica struktura podatkov. Podobno je izbirna vrsta kjer najprej poiščemo minimalni element in postavimo minimalni element na začetek. Enak postopek ponovite za preostale elemente.
Algoritem za razvrščanje kopice
Za rešitev težave sledite spodnji zamisli:
a b c številke
Priporočena težava Prosimo, da jo najprej rešite med VADJO, preden nadaljujete z rešitvijo Rešite težavoNajprej pretvorite matriko v podatkovno strukturo kopice z uporabo heapify, nato enega za drugim izbrišite korensko vozlišče največje kopice in ga nadomestite z zadnjim vozliščem v kopici ter nato kopičite koren kopice. Ta postopek ponavljajte, dokler velikost kopice ni večja od 1.
- Zgradite kopico iz podane vhodne matrike.
- Ponavljajte naslednje korake, dokler kopica ne vsebuje samo enega elementa:
- Zamenjajte korenski element kopice (ki je največji element) z zadnjim elementom kopice.
- Odstranite zadnji element kopice (ki je zdaj v pravilnem položaju).
- Zložite preostale elemente kopice.
- Razvrščeno matriko dobimo z obračanjem vrstnega reda elementov v vhodni matriki.
Podrobno delo razvrščanja kopice
Da bi jasneje razumeli razvrščanje kopice, vzemimo nerazvrščeno matriko in jo poskusimo razvrstiti z razvrščanjem kopice.
Razmislite o matriki: arr[] = {4, 10, 3, 5, 1}.Zgradite celotno binarno drevo: Iz matrike sestavite celotno binarno drevo.
Algoritem za razvrščanje kopice | Zgradite celotno binarno drevo
Pretvori v največji kup: Nato je naloga sestaviti drevo iz te nerazvrščene matrike in ga poskusiti pretvoriti v največja kopica.
- Če želite preoblikovati kopico v največjo kopico, mora biti nadrejeno vozlišče vedno večje ali enako podrejenim vozliščem
- Tukaj, v tem primeru, kot nadrejeno vozlišče 4 je manjše od podrejenega vozlišča 10, zato jih zamenjajte, da zgradite največji kup.
- zdaj, 4 saj je starš manjši od otroka 5 , tako znova zamenjajte oboje in nastala kopica in matrika bi morala biti takšna:
Algoritem za razvrščanje kopice | Max Heapify je sestavil binarno drevo
Izvedite razvrščanje kopice: Odstranite največji element v vsakem koraku (tj. premaknite ga na končni položaj in ga odstranite), nato pa upoštevajte preostale elemente in jih preoblikujte v največji kup.
- Izbrišite korenski element (10) iz največjega kupa. Če želite izbrisati to vozlišče, ga poskusite zamenjati z zadnjim vozliščem, tj. (1). Ko odstranite korenski element, ga znova kopičite, da ga pretvorite v največji kup.
- Dobljena kopica in matrika bi morala izgledati takole:
Algoritem za razvrščanje kopice | Odstranite največ iz korena in povečajte največ
- Ponovite zgornje korake in videti bo takole:
Algoritem za razvrščanje kopice | Odstranite naslednji maksimum iz korena nad max heapify
- Zdaj znova odstranite koren (tj. 3) in izvedite heapify.
Algoritem za razvrščanje kopice | Ponovite prejšnji korak
- Zdaj, ko je koren še enkrat odstranjen, je razvrščen. in razvrščena matrika bo podobna arr[] = {1, 3, 4, 5, 10} .
Algoritem za razvrščanje kopice | Končna razvrščena matrika
Implementacija 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[največji]) največji = l; // Če je desni otrok večji od največjega // do sedaj if (r< N && arr[r]>arr[največji]) največji = r; // Če največje ni koren if (največje != i) { swap(arr[i], arr[largest]); // Rekurzivno kopiči prizadeto // poddrevo heapify(arr, N, največji); } } // Glavna funkcija za razvrščanje kopice void heapSort(int arr[], int N) { // Zgradi kopico (preuredi niz) za (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Enega za drugim ekstrahiraj element // iz kopice za (int i = N - 1; i> 0; i--) { // Premakni trenutni koren na konec swap(arr[0], arr[i]); // pokliči max heapify na zmanjšani kopici heapify(arr, i, 0); } } // Pomožna funkcija za tiskanje matrike 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[največji]) največji = levo; // Če je desni otrok večji od največjega // do sedaj if (desno< N && arr[right]>arr[največji]) največji = desno; // Zamenjaj in nadaljuj s kopičenjem // če root ni največji // Če največji ni root if (largest != i) { swap(&arr[i], &arr[largest]); // Rekurzivno kopiči prizadeto // poddrevo heapify(arr, N, največji); } } // Glavna funkcija za razvrščanje kopice void heapSort(int arr[], int N) { // Zgradi največjo kopico za (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, i); // Razvrščanje kopice za (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]); // Heapify root element // za pridobitev najvišjega elementa // root znova heapify(arr, i, 0); } } // Pomožna funkcija za tiskanje matrike 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_.> 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); // Enega za drugim ekstrahiraj element iz kopice za (int i = N - 1; i> 0; i--) { // Premakni trenutni koren na konec int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // pokliči max heapify na zmanjšani kopici heapify(arr, i, 0); } } // Za kopičenje poddrevesa, ukoreninjenega z vozliščem i, ki je // indeks v arr[]. n je velikost kopice void heapify(int arr[], int N, int i) { int največji = i; // Inicializiraj največji kot koren int l = 2 * i + 1; // levo = 2*i + 1 int r = 2 * i + 2; // desno = 2*i + 2 // Če je levi podrejeni večji od korena if (l< N && arr[l]>arr[največji]) največji = l; // Če je desni otrok večji od največjega doslej, če (r< N && arr[r]>arr[največji]) največji = r; // Če največji ni koren if (največji != i) { int swap = arr[i]; arr[i] = arr[največji]; arr[največji] = zamenjava; // Rekurzivno kopiči prizadeto poddrevo heapify(arr, N, največji); } } /* Pomožna funkcija za tiskanje niza velikosti n */ static void printArray(int arr[]) { int N = arr.length; za (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); // Enega za drugim ekstrahiraj element iz kopice za (int i = N - 1; i> 0; i--) { // Premakni trenutni koren na konec int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // pokliči max heapify na zmanjšani kopici heapify(arr, i, 0); } } // Za kopičenje poddrevesa, ukoreninjenega z vozliščem i, ki je // indeks v arr[]. n je velikost kopice void heapify(int[] arr, int N, int i) { int največji = i; // Inicializiraj največji kot koren int l = 2 * i + 1; // levo = 2*i + 1 int r = 2 * i + 2; // desno = 2*i + 2 // Če je levi podrejeni večji od korena if (l< N && arr[l]>arr[največji]) največji = l; // Če je desni otrok večji od največjega doslej, če (r< N && arr[r]>arr[največji]) največji = r; // Če največji ni koren if (največji != i) { int swap = arr[i]; arr[i] = arr[največji]; arr[največji] = zamenjava; // Rekurzivno kopiči prizadeto poddrevo heapify(arr, N, največji); } } /* Pomožna funkcija za tiskanje niza velikosti n */ static void printArray(int[] arr) { int N = arr.Length; za (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); // Enega za drugim ekstrahiraj element iz kopice za (var i = N - 1; i> 0; i--) { // Premakni trenutni koren na konec var temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // pokliči max heapify na zmanjšani kopici heapify(arr, i, 0); } } // Za kopičenje poddrevesa, ukoreninjenega z vozliščem i, ki je // indeks v arr[]. n je velikost kopične funkcije heapify(arr, N, i) { var larger = i; // Inicializiraj največjo kot korensko var l = 2 * i + 1; // levo = 2*i + 1 var r = 2 * i + 2; // desno = 2*i + 2 // Če je levi podrejeni večji od korena if (l< N && arr[l]>arr[največji]) največji = l; // Če je desni otrok večji od največjega doslej, če (r< N && arr[r]>arr[največji]) največji = r; // Če največje ni koren if (največje != i) { var swap = arr[i]; arr[i] = arr[največji]; arr[največji] = zamenjava; // Rekurzivno kopiči prizadeto poddrevo heapify(arr, N, največji); } } /* Pomožna funkcija za tiskanje niza velikosti n */ function printArray(arr) { var N = arr.length; za (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[$največji]) $največji = $l; // Če je desni otrok večji od največjega doslej if ($r< $N && $arr[$r]>$arr[$največji]) $največji = $r; // Če največji ni koren if ($največji != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$največji]; $arr[$največji] = $swap; // Rekurzivno heapify prizadetega poddrevesa heapify($arr, $N, $largest); } } // glavna funkcija za razvrščanje kopice, funkcija heapSort(&$arr, $N) { // Gradi kopico (preuredi niz) za ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // Enega za drugim ekstrahiraj element iz kopice za ($i = $N-1; $i> 0; $i--) { // Premakni trenutni koren na konec $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // pokliči max heapify na zmanjšani kopici heapify($arr, $i, 0); } } /* Pomožna funkcija za tiskanje niza velikosti n */ funkcija 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> Izhod
Sorted array is 5 6 7 11 12 13>
Analiza kompleksnosti Razvrščanje kopice
Časovna zapletenost: O(N log N)
Pomožni prostor: O(log n), zaradi rekurzivnega sklada klicev. Vendar pa je lahko pomožni prostor O(1) za iterativno izvedbo.
Pomembne točke o razvrščanju kopice:
- Razvrščanje kopice je algoritem na mestu.
- Njegova tipična izvedba ni stabilna, vendar jo je mogoče narediti stabilno (glejte to )
- Običajno 2-3 krat počasneje kot dobro implementirano QuickSort . Razlog za počasnost je pomanjkanje lokalnosti referenčnih podatkov.
Prednosti Heap Sort:
- Učinkovita časovna kompleksnost: Razvrščanje kopice ima v vseh primerih časovno kompleksnost O(n log n). Zaradi tega je učinkovit pri razvrščanju velikih naborov podatkov. The dnevnik n faktor izhaja iz višine binarne kopice in zagotavlja, da algoritem ohranja dobro delovanje tudi z velikim številom elementov.
- Poraba pomnilnika – Poraba pomnilnika je lahko minimalna (s pisanjem iterativnega heapify() namesto rekurzivnega). Torej poleg tega, kar je potrebno za shranjevanje začetnega seznama elementov, ki jih je treba razvrstiti, za delovanje ne potrebuje dodatnega pomnilniškega prostora
- Preprostost – Lažje ga je razumeti kot druge enako učinkovite algoritme za razvrščanje, ker ne uporablja naprednih konceptov računalništva, kot je rekurzija.
Slabosti Heap Sort:
- drago : Razvrščanje kopice je drago, saj so konstante višje v primerjavi z razvrščanjem z združevanjem, tudi če je časovna kompleksnost O(n Log n) za oba.
- Nestabilen : Razvrščanje kopice je nestabilno. Lahko preuredi relativni vrstni red.
- Učinkovito: Razvrščanje kopice ni zelo učinkovito pri delu z zelo kompleksnimi podatki.
Pogosto zastavljena vprašanja v zvezi z razvrščanjem kopice
Q1. Kateri sta dve fazi razvrščanja kopice?
Algoritem razvrščanja kopice je sestavljen iz dveh faz. V prvi fazi se polje pretvori v največji kup. V drugi fazi se najvišji element odstrani (tj. tisti v korenu drevesa), preostali elementi pa se uporabijo za ustvarjanje novega največjega kupa.
Q2. Zakaj Heap Sort ni stabilen?
Algoritem za razvrščanje kopice ni stabilen algoritem, ker arr[i] zamenjamo z arr[0] v heapSort(), kar lahko spremeni relativno vrstni red enakovrednih ključev.
nginx
Q3. Ali je Heap Sort primer algoritma razdeli in vladaj?
Razvrščanje kopice je NE sploh algoritem deli in vladaj. Za učinkovito razvrščanje elementov uporablja podatkovno strukturo kopice in ne pristopa deli in vladaj za razvrščanje elementov.
Q4. Kateri algoritem razvrščanja je boljši – Heap sort ali Merge Sort?
Odgovor je v primerjavi njihove časovne zahtevnosti in prostorskih zahtev. Razvrščanje spajanjem je nekoliko hitrejše od razvrščanja kopice. Po drugi strani pa razvrščanje z združevanjem zahteva dodaten pomnilnik. Glede na zahteve je treba izbrati, katerega uporabiti.
V5. Zakaj je Heap sort boljši od Selection sort?
Razvrščanje kopice je podobno izbirnemu razvrščanju, vendar z boljšim načinom za pridobitev največjega elementa. Izkorišča podatkovno strukturo kopice, da dobi največji element v konstantnem času