In diesem Tutorial erfahren Sie, wie der Heap-Sortieralgorithmus funktioniert. Außerdem finden Sie Arbeitsbeispiele für die Heap-Sortierung in C, C ++, Java und Python.
Heap Sort ist ein beliebter und effizienter Sortieralgorithmus in der Computerprogrammierung. Um zu lernen, wie der Heap-Sortieralgorithmus geschrieben wird, müssen zwei Arten von Datenstrukturen bekannt sein - Arrays und Bäume.
Der anfängliche Satz von Zahlen, den wir sortieren möchten, wird in einem Array gespeichert, z. B. (10, 3, 76, 34, 23, 32)und nach dem Sortieren erhalten wir ein sortiertes Array(3,10,23,32,34,76)
Die Heap-Sortierung visualisiert die Elemente des Arrays als eine spezielle Art eines vollständigen Binärbaums, der als Heap bezeichnet wird.
Voraussetzung ist, dass Sie über eine vollständige Binärbaum- und Heap-Datenstruktur Bescheid wissen.
Beziehung zwischen Array-Indizes und Baumelementen
Ein vollständiger Binärbaum hat eine interessante Eigenschaft, mit der wir die Kinder und Eltern eines beliebigen Knotens finden können.
Wenn der Index eines Elements im Array i ist, wird das Element im Index 2i+1zum linken untergeordneten Element und das Element im 2i+2Index zum rechten untergeordneten Element . Außerdem ist das übergeordnete Element eines Elements am Index i durch die Untergrenze von gegeben (i-1)/2.
Beziehung zwischen Array- und Heap-Indizes
Lass es uns testen,
Linkes Kind von 1 (Index 0) = Element in (2 * 0 + 1) Index = Element in 1 Index = 12 Rechtes Kind von 1 = Element in (2 * 0 + 2) Index = Element in 2 Index = 9 Ähnlich Linkes Kind von 12 (Index 1) = Element in (2 * 1 + 1) Index = Element in 3 Index = 5 Rechtes Kind von 12 = Element in (2 * 1 + 2) Index = Element in 4 Index = 6
Lassen Sie uns auch bestätigen, dass die Regeln für die Suche nach Eltern eines Knotens gelten
Elternteil von 9 (Position 2) = (2-1) / 2 = ½ = 0,5 ~ 0 Index = 1 Elternteil von 12 (Position 1) = (1-1) / 2 = 0 Index = 1
Das Verständnis dieser Zuordnung von Array-Indizes zu Baumpositionen ist entscheidend für das Verständnis der Funktionsweise der Heap-Datenstruktur und der Verwendung zur Implementierung der Heap-Sortierung.
Was ist die Heap-Datenstruktur?
Heap ist eine spezielle baumbasierte Datenstruktur. Ein Binärbaum soll einer Heap-Datenstruktur folgen, wenn
- Es ist ein vollständiger Binärbaum
- Alle Knoten in der Baumstruktur folgen der Eigenschaft, dass sie größer als ihre untergeordneten Elemente sind, dh das größte Element befindet sich an der Wurzel und sowohl an ihren untergeordneten Elementen als auch kleiner als die Wurzel und so weiter. Ein solcher Heap wird als Max-Heap bezeichnet. Wenn stattdessen alle Knoten kleiner als ihre untergeordneten Knoten sind, wird dies als Min-Heap bezeichnet
Das folgende Beispieldiagramm zeigt Max-Heap und Min-Heap.
Max Heap und Min Heap
Um mehr darüber zu erfahren, besuchen Sie bitte Heap Data Structure.
Wie man einen Baum "häuft"
Ausgehend von einem vollständigen Binärbaum können wir ihn in einen Max-Heap ändern, indem wir eine Funktion namens heapify für alle Nicht-Blatt-Elemente des Heaps ausführen.
Da Heapify Rekursion verwendet, kann es schwierig sein, dies zu erfassen. Denken wir also zuerst darüber nach, wie Sie einen Baum mit nur drei Elementen häufen würden.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify Basisfälle
Das obige Beispiel zeigt zwei Szenarien - eines, in dem die Wurzel das größte Element ist und wir nichts tun müssen. Und eine andere, bei der die Wurzel als Kind ein größeres Element hatte und wir tauschen mussten, um die Max-Heap-Eigenschaft beizubehalten.
Wenn Sie zuvor mit rekursiven Algorithmen gearbeitet haben, haben Sie wahrscheinlich festgestellt, dass dies der Basisfall sein muss.
Stellen wir uns nun ein anderes Szenario vor, in dem es mehr als eine Ebene gibt.
So häufen Sie das Stammelement an, wenn seine Teilbäume bereits maximale Heaps sind
Das oberste Element ist kein Max-Heap, aber alle Unterbäume sind Max-Heaps.
Um die Eigenschaft max-heap für den gesamten Baum beizubehalten, müssen wir 2 weiter nach unten drücken, bis die richtige Position erreicht ist.
So häufen Sie das Stammelement an, wenn seine Teilbäume Max-Heaps sind
Thus, to maintain the max-heap property in a tree where both sub-trees are max-heaps, we need to run heapify on the root element repeatedly until it is larger than its children or it becomes a leaf node.
We can combine both these conditions in one heapify function as
void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) )
This function works for both the base case and for a tree of any size. We can thus move the root element to the correct position to maintain the max-heap status for any tree size as long as the sub-trees are max-heaps.
Build max-heap
To build a max-heap from any tree, we can thus start heapifying each sub-tree from the bottom up and end up with a max-heap after the function is applied to all the elements including the root element.
Bei einem vollständigen Baum ist der erste Index eines Nicht-Blattknotens gegeben durch n/2 - 1. Alle anderen Knoten danach sind Blattknoten und müssen daher nicht gehäuft werden.
So können wir einen maximalen Heap als erstellen
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Erstellen Sie ein Array und berechnen Sie i 
Schritte zum Erstellen des maximalen Heaps für die Heap-Sortierung 
Schritte zum Erstellen des maximalen Heaps für die Heap-Sortierung 
Schritte zum Erstellen des maximalen Heaps für die Heap-Sortierung
Wie im obigen Diagramm gezeigt, häufen wir zunächst die kleinsten Bäume und bewegen uns schrittweise nach oben, bis wir das Wurzelelement erreichen.
Wenn Sie bis hierher alles verstanden haben, herzlichen Glückwunsch, sind Sie auf dem Weg, die Heap-Sorte zu meistern.
Wie funktioniert die Heap-Sortierung?
- Da der Baum die Max-Heap-Eigenschaft erfüllt, wird das größte Element am Stammknoten gespeichert.
- Swap: Entfernen Sie das Wurzelelement und platzieren Sie es am Ende des Arrays (n-te Position). Platzieren Sie das letzte Element des Baums (Heap) an der freien Stelle.
- Entfernen: Reduzieren Sie die Größe des Heaps um 1.
- Heapify: Heapify das Wurzelelement erneut, so dass wir das höchste Element an der Wurzel haben.
- Der Vorgang wird wiederholt, bis alle Elemente der Liste sortiert sind.
Tauschen, entfernen und häufen
Der folgende Code zeigt die Operation.
// Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); )
Beispiele für Python, Java und C / C ++
Python Java C C ++ # Heap Sort in python def heapify(arr, n, i): # Find largest among root and children largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r # If root is not largest, swap with largest and continue heapifying if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build max heap for i in range(n//2, -1, -1): heapify(arr, n, i) for i in range(n-1, 0, -1): # Swap arr(i), arr(0) = arr(0), arr(i) # Heapify root element heapify(arr, i, 0) arr = (1, 12, 9, 5, 6, 10) heapSort(arr) n = len(arr) print("Sorted array is") for i in range(n): print("%d " % arr(i), end='')
// Heap Sort in Java public class HeapSort ( public void sort(int arr()) ( int n = arr.length; // Build max heap for (int i = n / 2 - 1; i>= 0; i--) ( heapify(arr, n, i); ) // Heap sort for (int i = n - 1; i>= 0; i--) ( int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // Heapify root element heapify(arr, i, 0); ) ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l arr(largest)) largest = l; if (r arr(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int swap = arr(i); arr(i) = arr(largest); arr(largest) = swap; heapify(arr, n, largest); ) ) // Function to print an array 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 code public static void main(String args()) ( int arr() = ( 1, 12, 9, 5, 6, 10 ); HeapSort hs = new HeapSort(); hs.sort(arr); System.out.println("Sorted array is"); printArray(arr); ) )
// Heap Sort in C #include // Function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) ) // Main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) printf("%d ", arr(i)); printf(""); ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); printf("Sorted array is "); printArray(arr, n); )
// Heap Sort in C++ #include using namespace std; void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(arr(i), arr(largest)); heapify(arr, n, largest); ) ) // main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(arr(0), arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) cout << arr(i) << " "; cout << ""; ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); cout << "Sorted array is "; printArray(arr, n); )
Komplexität der Heap-Sortierung
Heap Sort hat O(nlog n)zeitliche Komplexität für alle Fälle (bester Fall, durchschnittlicher Fall und schlechtester Fall).
Lassen Sie uns den Grund dafür verstehen. Die Höhe eines vollständigen Binärbaums mit n Elementen beträgtlog n
As we have seen earlier, to fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it.
In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps.
During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log n ~ nlog n.
During the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes log n worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is also nlog n.
Also since the build_max_heap and heap_sort steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of nlog n.
Also it performs sorting in O(1) space complexity. Compared with Quick Sort, it has a better worst case ( O(nlog n) ). Quick Sort has complexity O(n^2) for worst case. But in other cases, Quick Sort is fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.
Heap Sort Applications
Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort's running time and constant O(1) upper bound on its auxiliary storage.
Obwohl Heap Sort O(n log n)selbst im schlimmsten Fall zeitlich komplex ist , verfügt es nicht über mehr Anwendungen (im Vergleich zu anderen Sortieralgorithmen wie Quick Sort, Merge Sort). Die zugrunde liegende Datenstruktur, Heap, kann jedoch effizient verwendet werden, wenn das kleinste (oder größte) Element aus der Liste der Elemente extrahiert werden soll, ohne dass die verbleibenden Elemente in der sortierten Reihenfolge gehalten werden müssen. Zum Beispiel Prioritätswarteschlangen.
