Heap-Sortierung ist eine vergleichsbasierte Sortiertechnik, die auf basiert Binärer Heap Datenstruktur. Es ähnelt dem Auswahl sortieren wobei wir zuerst das minimale Element finden und das minimale Element am Anfang platzieren. Wiederholen Sie den gleichen Vorgang für die restlichen Elemente.
Heap-Sortieralgorithmus
Um das Problem zu lösen, befolgen Sie die folgende Idee:
Empfohlenes Problem Bitte lösen Sie es zuerst auf PRAXIS, bevor Sie mit der Lösung „Problem lösen“ fortfahrenKonvertieren Sie zuerst das Array mithilfe von Heapify in eine Heap-Datenstruktur, löschen Sie dann nacheinander den Wurzelknoten des Max-Heaps, ersetzen Sie ihn durch den letzten Knoten im Heap und stapeln Sie dann den Wurzelknoten des Heaps. Wiederholen Sie diesen Vorgang, bis die Heap-Größe größer als 1 ist.
- Erstellen Sie einen Heap aus dem angegebenen Eingabearray.
- Wiederholen Sie die folgenden Schritte, bis der Heap nur noch ein Element enthält:
- Tauschen Sie das Wurzelelement des Heaps (das größte Element) mit dem letzten Element des Heaps aus.
- Entfernen Sie das letzte Element des Heaps (das sich jetzt an der richtigen Position befindet).
- Heapen Sie die verbleibenden Elemente des Heaps.
- Das sortierte Array wird durch Umkehren der Reihenfolge der Elemente im Eingabearray erhalten.
Detaillierte Funktionsweise der Heap-Sortierung
Um die Heap-Sortierung besser zu verstehen, nehmen wir ein unsortiertes Array und versuchen, es mithilfe der Heap-Sortierung zu sortieren.
Betrachten Sie das Array: arr[] = {4, 10, 3, 5, 1}.Erstellen Sie einen vollständigen Binärbaum: Erstellen Sie aus dem Array einen vollständigen Binärbaum.
Heap-Sortieralgorithmus | Erstellen Sie einen vollständigen Binärbaum
In maximalen Heap umwandeln: Danach besteht die Aufgabe darin, aus diesem unsortierten Array einen Baum zu erstellen und zu versuchen, ihn in einen Baum umzuwandeln Maximaler Haufen.
- Um einen Heap in einen Max-Heap umzuwandeln, sollte der übergeordnete Knoten immer größer oder gleich den untergeordneten Knoten sein
- Hier in diesem Beispiel als übergeordneter Knoten 4 ist kleiner als der untergeordnete Knoten 10, Tauschen Sie sie daher aus, um einen Max-Heap zu erstellen.
- Jetzt, 4 da ein Elternteil kleiner ist als das Kind 5 , tauschen Sie also beide erneut aus und der resultierende Heap und das Array sollten wie folgt aussehen:
Heap-Sortieralgorithmus | Max Heapify hat einen Binärbaum erstellt
Führen Sie eine Heap-Sortierung durch: Entfernen Sie in jedem Schritt das maximale Element (d. h. verschieben Sie es an die Endposition und entfernen Sie es), berücksichtigen Sie dann die verbleibenden Elemente und wandeln Sie es in einen maximalen Heap um.
- Löschen Sie das Stammelement (10) vom maximalen Heap. Um diesen Knoten zu löschen, versuchen Sie, ihn mit dem letzten Knoten auszutauschen, d. h. (1). Nachdem Sie das Root-Element entfernt haben, heapen Sie es erneut, um es in maximalen Heap umzuwandeln.
- Der resultierende Heap und das resultierende Array sollten wie folgt aussehen:
Heap-Sortieralgorithmus | Entfernen Sie das Maximum aus der Wurzel und heben Sie das Maximum auf
- Wiederholen Sie die obigen Schritte und es sieht wie folgt aus:
Heap-Sortieralgorithmus | Entfernen Sie das nächste Maximum aus der Wurzel und maximieren Sie es
- Entfernen Sie nun erneut den Root (also 3) und führen Sie Heapify durch.
Heap-Sortieralgorithmus | Wiederholen Sie den vorherigen Schritt
- Wenn nun die Wurzel erneut entfernt wird, wird sie sortiert. und das sortierte Array wird wie folgt aussehen arr[] = {1, 3, 4, 5, 10} .
Heap-Sortieralgorithmus | Endgültiges sortiertes Array
Implementierung der Heap-Sortierung
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[größte]) größte = l; // Wenn das rechte Kind größer als das größte ist // bisher if (r< N && arr[r]>arr[größte]) größte = r; // Wenn der größte nicht root ist if (largest != i) { swap(arr[i], arr[largest]); // Den betroffenen // Teilbaum rekursiv häufen heapify(arr, N, most); } } // Hauptfunktion für die Heap-Sortierung void heapSort(int arr[], int N) { // Heap erstellen (Array neu anordnen) for (int i = N / 2 - 1; i>= 0; i--) heapify(arr, N, i); // Einer nach dem anderen ein Element // aus dem Heap extrahieren for (int i = N - 1; i> 0; i--) { // Aktuelle Wurzel an das Ende verschieben swap(arr[0], arr[i]); // max heapify auf dem reduzierten Heap aufrufen heapify(arr, i, 0); } } // Eine Hilfsfunktion zum Drucken eines Arrays der Größe 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[größte]) größte = links; // Wenn das rechte Kind größer als das größte ist // bisher if (right< N && arr[right]>arr[größte]) größte = rechts; // Tauschen und weiter häufen // wenn root nicht der größte ist // Wenn der größte nicht root ist if (largest != i) { swap(&arr[i], &arr[largest]); // Den betroffenen // Teilbaum rekursiv häufen heapify(arr, N, most); } } // Hauptfunktion für die Heap-Sortierung void heapSort(int arr[], int N) { // Maximalen Heap erstellen für (int i = N / 2 - 1; i>= 0; i--) heapify(arr , N, i); // Heap-Sortierung for (int i = N - 1; i>= 0; i--) { swap(&arr[0], &arr[i]); // Root-Element aufhäufen // um das höchste Element bei // Root erneut zu erhalten heapify(arr, i, 0); } } // Eine Hilfsfunktion zum Drucken eines Arrays der Größe 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); // Eins nach dem anderen ein Element aus dem Heap extrahieren for (int i = N - 1; i> 0; i--) { // Aktuelle Wurzel an das Ende verschieben int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // max heapify auf dem reduzierten Heap aufrufen heapify(arr, i, 0); } } // Um einen Teilbaum zu häufen, dessen Wurzel Knoten i ist, der // ein Index in arr[] ist. n ist die Größe des Heaps. void heapify(int arr[], int N, int i) { int most = i; // Größtes als Root initialisieren int l = 2 * i + 1; // left = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // Wenn das linke Kind größer als die Wurzel ist, if (l< N && arr[l]>arr[größte]) größte = l; // Wenn das rechte Kind größer als das bisher größte ist, if (r< N && arr[r]>arr[größte]) größte = r; // Wenn der Größte nicht root ist if (größter != i) { int swap = arr[i]; arr[i] = arr[größte]; arr[größte] = swap; // Den betroffenen Teilbaum rekursiv häufen heapify(arr, N, most); } } /* Eine Hilfsfunktion zum Drucken eines Arrays der Größe n */ static void printArray(int arr[]) { int N = arr.length; für (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); // Eins nach dem anderen ein Element aus dem Heap extrahieren for (int i = N - 1; i> 0; i--) { // Aktuelle Wurzel an das Ende verschieben int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // max heapify auf dem reduzierten Heap aufrufen heapify(arr, i, 0); } } // Um einen Teilbaum zu häufen, dessen Wurzel Knoten i ist, der // ein Index in arr[] ist. n ist die Größe des Heaps. void heapify(int[] arr, int N, int i) { int most = i; // Größtes als Root initialisieren int l = 2 * i + 1; // left = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // Wenn das linke Kind größer als die Wurzel ist, if (l< N && arr[l]>arr[größte]) größte = l; // Wenn das rechte Kind größer als das bisher größte ist, if (r< N && arr[r]>arr[größte]) größte = r; // Wenn der Größte nicht root ist if (größter != i) { int swap = arr[i]; arr[i] = arr[größte]; arr[größte] = swap; // Den betroffenen Teilbaum rekursiv häufen heapify(arr, N, most); } } /* Eine Hilfsfunktion zum Drucken eines Arrays der Größe n */ static void printArray(int[] arr) { int N = arr.Length; für (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); // Eins nach dem anderen ein Element aus dem Heap extrahieren for (var i = N - 1; i> 0; i--) { // Aktuelle Wurzel an das Ende verschieben var temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // max heapify auf dem reduzierten Heap aufrufen heapify(arr, i, 0); } } // Um einen Teilbaum zu häufen, dessen Wurzel Knoten i ist, der // ein Index in arr[] ist. n ist die Größe der Heap-Funktion heapify(arr, N, i) { var most = i; // Größte als Wurzel initialisieren var l = 2 * i + 1; // left = 2*i + 1 var r = 2 * i + 2; // right = 2*i + 2 // Wenn das linke Kind größer als die Wurzel ist, if (l< N && arr[l]>arr[größte]) größte = l; // Wenn das rechte Kind größer als das bisher größte ist, if (r< N && arr[r]>arr[größte]) größte = r; // Wenn der größte nicht root ist if (größter != i) { var swap = arr[i]; arr[i] = arr[größte]; arr[größte] = swap; // Den betroffenen Teilbaum rekursiv häufen heapify(arr, N, most); } } /* Eine Hilfsfunktion zum Drucken eines Arrays der Größe n */ function printArray(arr) { var N = arr.length; für (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[$largest]) $largest = $l; // Wenn das rechte Kind größer als das bisher größte ist, if ($r< $N && $arr[$r]>$arr[$largest]) $largest = $r; // Wenn der größte nicht root ist if ($largest != $i) { $swap = $arr[$i]; $arr[$i] = $arr[$largest]; $arr[$largest] = $swap; // Den betroffenen Teilbaum rekursiv aufhäufen heapify($arr, $N, $largest); } } // Hauptfunktion zum Ausführen der Heap-Sortierfunktion heapSort(&$arr, $N) { // Heap erstellen (Array neu anordnen) für ($i = $N / 2 - 1; $i>= 0; $i- -) heapify($arr, $N, $i); // Eins nach dem anderen ein Element aus dem Heap extrahieren for ($i = $N-1; $i> 0; $i--) { // Aktuelle Wurzel an das Ende verschieben $temp = $arr[0]; $arr[0] = $arr[$i]; $arr[$i] = $temp; // max heapify auf dem reduzierten Heap aufrufen heapify($arr, $i, 0); } } /* Eine Hilfsfunktion zum Drucken eines Arrays der Größe n */ 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> Ausgabe
Sorted array is 5 6 7 11 12 13>
Komplexitätsanalyse von Heap-Sortierung
Zeitkomplexität: O(N log N)
Hilfsraum: O(log n), aufgrund des rekursiven Aufrufstapels. Für die iterative Implementierung kann der Hilfsraum jedoch O(1) sein.
Wichtige Punkte zur Heap-Sortierung:
- Heap-Sortierung ist ein In-Place-Algorithmus.
- Seine typische Implementierung ist nicht stabil, kann aber stabil gemacht werden (siehe Das )
- Typischerweise 2-3 mal langsamer als gut implementiert Schnelle Sorte . Der Grund für die Langsamkeit ist ein Mangel an Bezugslokalität.
Vorteile der Heap-Sortierung:
- Effiziente Zeitkomplexität: Heap Sort hat in allen Fällen eine zeitliche Komplexität von O(n log n). Dies macht es effizient zum Sortieren großer Datensätze. Der log n Der Faktor ergibt sich aus der Höhe des Binärheaps und stellt sicher, dass der Algorithmus auch bei einer großen Anzahl von Elementen eine gute Leistung beibehält.
- Speichernutzung - Die Speichernutzung kann minimal sein (durch Schreiben eines iterativen heapify() anstelle eines rekursiven). Abgesehen von dem, was zum Speichern der anfänglichen Liste der zu sortierenden Elemente erforderlich ist, benötigt es zum Funktionieren keinen zusätzlichen Speicherplatz
- Einfachheit – Es ist einfacher zu verstehen als andere ebenso effiziente Sortieralgorithmen, da es keine fortgeschrittenen Informatikkonzepte wie Rekursion verwendet.
Nachteile der Heap-Sortierung:
- Teuer : Heap-Sortierung ist kostspielig, da die Konstanten im Vergleich zur Zusammenführungssortierung höher sind, selbst wenn die Zeitkomplexität für beide O(n Log n) ist.
- Instabil : Heap-Sortierung ist instabil. Es könnte die relative Reihenfolge ändern.
- Effizient: Heap Sort ist bei der Arbeit mit hochkomplexen Daten nicht sehr effizient.
Häufig gestellte Fragen zur Heap-Sortierung
Q1. Was sind die zwei Phasen der Heap-Sortierung?
Der Heap-Sortieralgorithmus besteht aus zwei Phasen. In der ersten Phase wird das Array in einen Max-Heap umgewandelt. Und in der zweiten Phase wird das höchste Element entfernt (d. h. das an der Baumwurzel) und die verbleibenden Elemente werden verwendet, um einen neuen maximalen Heap zu erstellen.
Q2. Warum ist Heap Sort nicht stabil?
Der Heap-Sortieralgorithmus ist kein stabiler Algorithmus, da wir in heapSort() arr[i] mit arr[0] austauschen, was die relative Reihenfolge der entsprechenden Schlüssel ändern könnte.
Q3. Ist Heap Sort ein Beispiel für den Divide and Conquer-Algorithmus?
Heap-Sortierung ist NICHT überhaupt ein Divide-and-Conquer-Algorithmus. Es verwendet eine Heap-Datenstruktur, um seine Elemente effizient zu sortieren, und keinen Divide-and-Conquer-Ansatz zum Sortieren der Elemente.
Q4. Welcher Sortieralgorithmus ist besser – Heap-Sortierung oder Merge-Sortierung?
Die Antwort liegt im Vergleich ihrer zeitlichen Komplexität und ihres Platzbedarfs. Die Merge-Sortierung ist etwas schneller als die Heap-Sortierung. Andererseits benötigt die Zusammenführungssortierung jedoch zusätzlichen Speicher. Je nach Anforderung sollte man wählen, welches man verwenden möchte.
F5. Warum ist die Heap-Sortierung besser als die Auswahl-Sortierung?
Die Heap-Sortierung ähnelt der Auswahlsortierung, bietet jedoch eine bessere Möglichkeit, das maximale Element zu erhalten. Es nutzt die Heap-Datenstruktur, um das maximale Element in konstanter Zeit zu erhalten