Hoop sorteren is een op vergelijking gebaseerde sorteertechniek gebaseerd op Binaire hoop data structuur. Het is vergelijkbaar met de selectie sorteren waar we eerst het minimumelement vinden en het minimumelement aan het begin plaatsen. Herhaal hetzelfde proces voor de overige elementen.
Heap-sorteeralgoritme
Om het probleem op te lossen, volgt u het onderstaande idee:
Aanbevolen probleem Los dit eerst op door te oefenen, voordat u verdergaat met de oplossing Probleem oplossenConverteer eerst de array naar een heap-gegevensstructuur met behulp van heapify, verwijder vervolgens één voor één het hoofdknooppunt van de Max-heap en vervang het door het laatste knooppunt in de heap en heapify vervolgens de hoofdknoop van de heap. Herhaal dit proces totdat de grootte van de hoop groter is dan 1.
- Bouw een heap op basis van de gegeven invoerarray.
- Herhaal de volgende stappen totdat de heap slechts één element bevat:
- Verwissel het hoofdelement van de heap (dat het grootste element is) met het laatste element van de heap.
- Verwijder het laatste element van de hoop (die nu op de juiste positie staat).
- Stapel de resterende elementen van de hoop op.
- De gesorteerde array wordt verkregen door de volgorde van de elementen in de invoerarray om te keren.
Gedetailleerde werking van heapsortering
Om heap sortering duidelijker te begrijpen, nemen we een ongesorteerde array en proberen deze te sorteren met behulp van heap sort.
Beschouw de array: arr[] = {4, 10, 3, 5, 1}.Bouw een volledige binaire boom: Bouw een volledige binaire boom uit de array.
Heap-sorteeralgoritme | Bouw een volledige binaire boom
Transformeren naar maximale heap: Daarna is het de taak om een boom te construeren uit die ongesorteerde array en deze te proberen om te zetten in maximale hoop.
- Om een heap in een max-heap te transformeren, moet het bovenliggende knooppunt altijd groter zijn dan of gelijk zijn aan de onderliggende knooppunten
- Hier, in dit voorbeeld, als het bovenliggende knooppunt 4 kleiner is dan het kindknooppunt 10, verwissel ze dus om een max-heap te bouwen.
- Nu, 4 omdat een ouder kleiner is dan het kind 5 , dus verwissel beide opnieuw en de resulterende heap en array zouden er als volgt uit moeten zien:
Heap-sorteeralgoritme | Max Heapify heeft een binaire boom geconstrueerd
Voer heap-sortering uit: Verwijder het maximale element bij elke stap (dat wil zeggen, verplaats het naar de eindpositie en verwijder dat) en beschouw vervolgens de resterende elementen en transformeer het in een maximale hoop.
- Verwijder het hoofdelement (10) van de maximale hoop. Om dit knooppunt te verwijderen, probeert u het te verwisselen met het laatste knooppunt, d.w.z. (1). Nadat u het rootelement hebt verwijderd, moet u het opnieuw ophopen om het om te zetten in max heap.
- De resulterende heap en array zouden er als volgt uit moeten zien:
Heap-sorteeralgoritme | Verwijder maximum uit root en max heapify
Hoe een script op Linux uit te voeren
- Herhaal bovenstaande stappen en het ziet er als volgt uit:
Heap-sorteeralgoritme | Verwijder het volgende maximum uit root en max heapify
- Verwijder nu de root (d.w.z. 3) opnieuw en voer heapify uit.
Heap-sorteeralgoritme | Herhaal de vorige stap
- Wanneer de wortel nu opnieuw wordt verwijderd, wordt deze gesorteerd. en de gesorteerde array zal er zo uitzien arr[] = {1, 3, 4, 5, 10} .
Heap-sorteeralgoritme | Uiteindelijk gesorteerde array
Implementatie van heapsortering
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[grootste]) grootste = l; // Als het rechterkind groter is dan het grootste // tot nu toe als (r< N && arr[r]>arr[grootste]) grootste = r; // Als de grootste geen root is if (grootste != i) { swap(arr[i], arr[grootste]); // Heapify recursief de getroffen // sub-boom heapify(arr, N, grootste); } } // Hoofdfunctie voor het sorteren van heap void heapSort(int arr[], int N) {// Bouw heap (array herschikken) voor (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Extraheer een element één voor één // uit heap for (int i = N - 1; i> 0; i--) {// Verplaats huidige root naar end swap(arr[0], arr[i]); // roep max heapify aan op de gereduceerde heap heapify(arr, i, 0); } } // Een hulpprogrammafunctie voor het afdrukken van een array met de grootte 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[grootste]) grootste = links; // Als het rechterkind groter is dan het grootste // tot nu toe als (juist< N && arr[right]>arr[grootste]) grootste = rechts; // Wissel en ga door met heapificeren // als de root niet de grootste is // Als de grootste niet de root is if (grootste != i) { swap(&arr[i], &arr[grootste]); // Heapify recursief de getroffen // sub-boom heapify(arr, N, grootste); } } // Hoofdfunctie voor heap sort void heapSort(int arr[], int N) {// Bouw max heap voor (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, ik); // Heap sorteren voor (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]); // Heapify root-element // om het hoogste element te krijgen bij // root opnieuw heapify(arr, i, 0); } } // Een hulpprogrammafunctie voor het afdrukken van een array met de grootte 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; ik--) heapify(arr, N, i); // Haal één voor één een element uit de heap voor (int i = N - 1; i> 0; i--) {// Verplaats de huidige root naar het einde int temp = arr[0]; arr[0] = arr[i]; arr[i] = temperatuur; // roep max heapify aan op de gereduceerde heap heapify(arr, i, 0); } } // Om een subboom te heapificeren die is geroot met knooppunt i, wat // een index is in arr[]. n is de grootte van de heap void heapify(int arr[], int N, int i) { int grootste = i; // Initialiseer de grootste als root int l = 2 * i + 1; // links = 2*i + 1 int r = 2 * i + 2; // rechts = 2*i + 2 // Als het linkerkind groter is dan de wortel als (l< N && arr[l]>arr[grootste]) grootste = l; // Als het rechterkind groter is dan de grootste tot nu toe als (r< N && arr[r]>arr[grootste]) grootste = r; // Als de grootste geen root is if (grootste != i) { int swap = arr[i]; arr[i] = arr[grootste]; arr[grootste] = ruilen; // Heapify recursief de betrokken subboom heapify(arr, N, grootste); } } /* Een hulpprogrammafunctie voor het afdrukken van een array met de grootte n */ static void printArray(int arr[]) { int N = arr.length; voor (int i = 0; ik< 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; ik--) heapify(arr, N, i); // Haal één voor één een element uit de heap voor (int i = N - 1; i> 0; i--) {// Verplaats de huidige root naar het einde int temp = arr[0]; arr[0] = arr[i]; arr[i] = temperatuur; // roep max heapify aan op de gereduceerde heap heapify(arr, i, 0); } } // Om een subboom te heapificeren die is geroot met knooppunt i, wat // een index is in arr[]. n is de grootte van de heap void heapify(int[] arr, int N, int i) { int grootste = i; // Initialiseer de grootste als root int l = 2 * i + 1; // links = 2*i + 1 int r = 2 * i + 2; // rechts = 2*i + 2 // Als het linkerkind groter is dan de wortel als (l< N && arr[l]>arr[grootste]) grootste = l; // Als het rechterkind groter is dan de grootste tot nu toe als (r< N && arr[r]>arr[grootste]) grootste = r; // Als de grootste geen root is if (grootste != i) { int swap = arr[i]; arr[i] = arr[grootste]; arr[grootste] = ruilen; // Heapify recursief de betrokken subboom heapify(arr, N, grootste); } } /* Een hulpprogrammafunctie voor het afdrukken van een array met de grootte n */ static void printArray(int[] arr) { int N = arr.Length; voor (int i = 0; ik< 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; ik--) heapify(arr, N, i); // Haal één voor één een element uit de heap voor (var i = N - 1; i> 0; i--) {// Verplaats de huidige root naar het einde var temp = arr[0]; arr[0] = arr[i]; arr[i] = temperatuur; // roep max heapify aan op de gereduceerde heap heapify(arr, i, 0); } } // Om een subboom te heapificeren die is geroot met knooppunt i, wat // een index is in arr[]. n is de grootte van de heapfunctie heapify(arr, N, i) { var grootste = i; // Initialiseer de grootste als root var l = 2 * i + 1; // links = 2*i + 1 var r = 2 * i + 2; // rechts = 2*i + 2 // Als het linkerkind groter is dan de wortel als (l< N && arr[l]>arr[grootste]) grootste = l; // Als het rechterkind groter is dan de grootste tot nu toe als (r< N && arr[r]>arr[grootste]) grootste = r; // Als grootste geen root is if (grootste != i) { var swap = arr[i]; arr[i] = arr[grootste]; arr[grootste] = ruilen; // Heapify recursief de betrokken subboom heapify(arr, N, grootste); } } /* Een hulpprogrammafunctie om een array met de grootte n af te drukken */ function printArray(arr) { var N = arr.length; voor (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[$grootste]) $grootste = $l; // Als het rechterkind groter is dan de grootste tot nu toe if ($r< $N && $arr[$r]>$arr[$grootste]) $grootste = $r; // Als grootste geen root is if ($grootste != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$grootste]; $arr[$grootste] = $wissel; // Heapify recursief de betrokken subboom heapify($arr, $N, $largest); } } // hoofdfunctie om de heap-sorteerfunctie uit te voeren heapSort(&$arr, $N) {// Bouw heap (herschik array) voor ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // Extraheer een element uit de heap voor ($i = $N-1; $i> 0; $i--) {// Verplaats de huidige root naar het einde $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // roep max heapify aan op de gereduceerde heap heapify($arr, $i, 0); } } /* Een hulpprogrammafunctie om een array met de grootte n af te drukken */ 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 # 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> Uitvoer
Sorted array is 5 6 7 11 12 13>
Complexiteitsanalyse van Hoop sorteren
Tijdcomplexiteit: O(N logboek N)
Hulpruimte: O(log n), vanwege de recursieve call-stack. Hulpruimte kan echter O(1) zijn voor iteratieve implementatie.
Belangrijke punten over Heap Sort:
- Heap sort is een in-place algoritme.
- De typische implementatie ervan is niet stabiel, maar kan wel stabiel worden gemaakt (zie dit )
- Meestal 2-3 keer langzamer dan goed geïmplementeerd Snel sorteren . De reden voor de traagheid is een gebrek aan referentielocatie.
Voordelen van heapsortering:
- Efficiënte tijdcomplexiteit: Heap Sort heeft in alle gevallen een tijdscomplexiteit van O(n log n). Dit maakt het efficiënt voor het sorteren van grote datasets. De log n De factor komt van de hoogte van de binaire heap en zorgt ervoor dat het algoritme goede prestaties behoudt, zelfs met een groot aantal elementen.
- Geheugengebruik - Het geheugengebruik kan minimaal zijn (door een iteratieve heapify() te schrijven in plaats van een recursieve). Dus afgezien van wat nodig is om de initiële lijst met te sorteren items vast te houden, heeft het geen extra geheugenruimte nodig om te werken
- Eenvoud – Het is eenvoudiger te begrijpen dan andere, even efficiënte sorteeralgoritmen, omdat er geen gebruik wordt gemaakt van geavanceerde computerwetenschappelijke concepten zoals recursie.
Nadelen van heapsortering:
- Duur : Heap-sortering is duur omdat de constanten hoger zijn in vergelijking met merge-sortering, zelfs als de tijdscomplexiteit voor beide O(n Log n) is.
- Onstabiel : Heap-sortering is instabiel. Het zou de relatieve volgorde kunnen herschikken.
- Efficiënt: Heap Sort is niet erg efficiënt bij het werken met zeer complexe gegevens.
Veelgestelde vragen met betrekking tot heapsortering
Q1. Wat zijn de twee fasen van Heap Sort?
Het heap sort-algoritme bestaat uit twee fasen. In de eerste fase wordt de array omgezet in een max heap. En in de tweede fase wordt het hoogste element verwijderd (d.w.z. dat bij de boomwortel) en worden de overige elementen gebruikt om een nieuwe maximale heap te creëren.
Vraag 2. Waarom is Heap Sort niet stabiel?
Het heap sort-algoritme is geen stabiel algoritme omdat we arr[i] verwisselen met arr[0] in heapSort(), wat de relatieve volgorde van de equivalente sleutels zou kunnen veranderen.
Q3. Is Heap Sort een voorbeeld van het verdeel en heers-algoritme?
Heap-soort is NIET helemaal geen verdeel en heers-algoritme. Het maakt gebruik van een heap-datastructuur om de elementen efficiënt te sorteren en niet van een verdeel-en-heers-aanpak om de elementen te sorteren.
Q4. Welk sorteeralgoritme is beter: heapsortering of samenvoegsortering?
Het antwoord ligt in de vergelijking van hun tijdscomplexiteit en ruimtevereisten. De samenvoegingssortering is iets sneller dan de heap-sortering. Maar aan de andere kant kost merge sort extra geheugen. Afhankelijk van de vereiste moet u kiezen welke u wilt gebruiken.
Vraag 5. Waarom is Heap-sortering beter dan Selectie-sortering?
Heap-sortering is vergelijkbaar met selectie-sortering, maar met een betere manier om het maximale element te verkrijgen. Het maakt gebruik van de heap-datastructuur om het maximale element in constante tijd te verkrijgen