In diesem Artikel werden wir den Heapsort-Algorithmus diskutieren. Die Heap-Sortierung verarbeitet die Elemente, indem sie mithilfe der Elemente des angegebenen Arrays den Min-Heap oder Max-Heap erstellt. Min-Heap oder Max-Heap stellt die Reihenfolge des Arrays dar, in der das Wurzelelement das minimale oder maximale Element des Arrays darstellt.

Die Heap-Sortierung führt grundsätzlich rekursiv zwei Hauptoperationen aus:

• Erstellen Sie einen Heap H mit den Elementen des Arrays.
• Löschen Sie wiederholt das Wurzelelement des in 1 gebildeten Heaps^stPhase.

Bevor wir mehr über die Heap-Sortierung erfahren, sehen wir uns zunächst eine kurze Beschreibung an Haufen.

Was ist ein Haufen?

Ein Heap ist ein vollständiger Binärbaum, und der Binärbaum ist ein Baum, in dem der Knoten die höchsten zwei untergeordneten Knoten haben kann. Ein vollständiger Binärbaum ist ein Binärbaum, in dem alle Ebenen außer der letzten Ebene, d. h. dem Blattknoten, vollständig gefüllt sein sollten und alle Knoten linksbündig ausgerichtet sein sollten.

Was ist Heap-Sortierung?

Heapsort ist ein beliebter und effizienter Sortieralgorithmus. Das Konzept der Heap-Sortierung besteht darin, die Elemente einzeln aus dem Heap-Teil der Liste zu entfernen und sie dann in den sortierten Teil der Liste einzufügen.

Heapsort ist der In-Place-Sortieralgorithmus.

Typvariablen Java

Sehen wir uns nun den Algorithmus der Heap-Sortierung an.

Algorithmus

 HeapSort(arr) BuildMaxHeap(arr) for i = length(arr) to 2 swap arr[1] with arr[i] heap_size[arr] = heap_size[arr] ? 1 MaxHeapify(arr,1) End 

BuildMaxHeap(arr)

 BuildMaxHeap(arr) heap_size(arr) = length(arr) for i = length(arr)/2 to 1 MaxHeapify(arr,i) End 

MaxHeapify(arr,i)

 MaxHeapify(arr,i) L = left(i) R = right(i) if L ? heap_size[arr] and arr[L] > arr[i] largest = L else largest = i if R ? heap_size[arr] and arr[R] > arr[largest] largest = R if largest != i swap arr[i] with arr[largest] MaxHeapify(arr,largest) End 

Funktionsweise des Heap-Sort-Algorithmus

Sehen wir uns nun die Funktionsweise des Heapsort-Algorithmus an.

Bei der Heap-Sortierung gibt es grundsätzlich zwei Phasen beim Sortieren von Elementen. Bei Verwendung des Heap-Sortieralgorithmus lauten sie wie folgt:

• Der erste Schritt umfasst die Erstellung eines Heaps durch Anpassen der Elemente des Arrays.
• Nach der Erstellung des Heaps entfernen Sie nun wiederholt das Stammelement des Heaps, indem Sie es an das Ende des Arrays verschieben, und speichern dann die Heap-Struktur mit den verbleibenden Elementen.

Sehen wir uns nun anhand eines Beispiels die Funktionsweise der Heap-Sortierung im Detail an. Um es besser zu verstehen, nehmen wir ein unsortiertes Array und versuchen, es mithilfe der Heap-Sortierung zu sortieren. Dadurch wird die Erklärung klarer und einfacher.

Zuerst müssen wir aus dem angegebenen Array einen Heap erstellen und ihn in einen maximalen Heap konvertieren.

Nach der Konvertierung des angegebenen Heaps in den maximalen Heap sind die Array-Elemente:

Als nächstes müssen wir das Wurzelelement löschen (89) vom maximalen Heap. Um diesen Knoten zu löschen, müssen wir ihn mit dem letzten Knoten tauschen, d.h. (elf). Nachdem wir das Root-Element gelöscht haben, müssen wir es erneut heapen, um es in maximalen Heap umzuwandeln.

Nach dem Austausch des Array-Elements 89 mit elf, und Konvertieren des Heaps in Max-Heap, die Elemente des Arrays sind -

Im nächsten Schritt müssen wir wiederum das Wurzelelement löschen (81) vom maximalen Heap. Um diesen Knoten zu löschen, müssen wir ihn mit dem letzten Knoten tauschen, d.h. (54). Nachdem wir das Root-Element gelöscht haben, müssen wir es erneut heapen, um es in maximalen Heap umzuwandeln.

Nach dem Austausch des Array-Elements 81 mit 54 und Konvertieren des Heaps in Max-Heap, die Elemente des Arrays sind -

Im nächsten Schritt müssen wir das Wurzelelement löschen (76) wieder vom maximalen Heap. Um diesen Knoten zu löschen, müssen wir ihn mit dem letzten Knoten tauschen, d.h. (9). Nachdem wir das Root-Element gelöscht haben, müssen wir es erneut heapen, um es in maximalen Heap umzuwandeln.

Nach dem Austausch des Array-Elements 76 mit 9 und Konvertieren des Heaps in Max-Heap, die Elemente des Arrays sind -

Im nächsten Schritt müssen wir erneut das Wurzelelement löschen (54) vom maximalen Heap. Um diesen Knoten zu löschen, müssen wir ihn mit dem letzten Knoten tauschen, d.h. (14). Nachdem wir das Root-Element gelöscht haben, müssen wir es erneut heapen, um es in maximalen Heap umzuwandeln.

Nach dem Austausch des Array-Elements 54 mit 14 und Konvertieren des Heaps in Max-Heap, die Elemente des Arrays sind -

Im nächsten Schritt müssen wir erneut das Wurzelelement löschen (22) vom maximalen Heap. Um diesen Knoten zu löschen, müssen wir ihn mit dem letzten Knoten tauschen, d.h. (elf). Nachdem wir das Root-Element gelöscht haben, müssen wir es erneut heapen, um es in maximalen Heap umzuwandeln.

Nach dem Austausch des Array-Elements 22 mit elf und Konvertieren des Heaps in Max-Heap, die Elemente des Arrays sind -

Im nächsten Schritt müssen wir erneut das Wurzelelement löschen (14) vom maximalen Heap. Um diesen Knoten zu löschen, müssen wir ihn mit dem letzten Knoten tauschen, d.h. (9). Nachdem wir das Root-Element gelöscht haben, müssen wir es erneut heapen, um es in maximalen Heap umzuwandeln.

Nach dem Austausch des Array-Elements 14 mit 9 und Konvertieren des Heaps in Max-Heap, die Elemente des Arrays sind -

Im nächsten Schritt müssen wir erneut das Wurzelelement löschen (elf) vom maximalen Heap. Um diesen Knoten zu löschen, müssen wir ihn mit dem letzten Knoten tauschen, d.h. (9). Nachdem wir das Root-Element gelöscht haben, müssen wir es erneut heapen, um es in maximalen Heap umzuwandeln.

Nach dem Austausch des Array-Elements elf mit 9, Die Elemente des Arrays sind -

Jetzt hat der Heap nur noch ein Element. Nach dem Löschen ist der Heap leer.

Switch-Methode Java

Nach Abschluss der Sortierung sind die Array-Elemente -

Jetzt ist das Array vollständig sortiert.

Komplexität der Heap-Sortierung

Sehen wir uns nun die zeitliche Komplexität der Heap-Sortierung im besten, durchschnittlichen und schlechtesten Fall an. Wir werden auch die räumliche Komplexität von Heapsort sehen.

1. Zeitkomplexität

Beste Fallkomplexität -Dies geschieht, wenn keine Sortierung erforderlich ist, d. h. das Array bereits sortiert ist. Die Zeitkomplexität der Heap-Sortierung beträgt im besten Fall O(n log). Durchschnittliche Fallkomplexität -Es tritt auf, wenn die Array-Elemente in einer durcheinandergebrachten Reihenfolge vorliegen, die nicht richtig aufsteigend und nicht richtig absteigend ist. Die durchschnittliche Fallzeitkomplexität der Heap-Sortierung beträgt O(n log n). Worst-Case-Komplexität -Es tritt auf, wenn die Array-Elemente in umgekehrter Reihenfolge sortiert werden müssen. Angenommen, Sie müssen die Array-Elemente in aufsteigender Reihenfolge sortieren, die Elemente jedoch in absteigender Reihenfolge. Die zeitliche Komplexität der Heap-Sortierung im schlimmsten Fall beträgt O(n log n).

Die zeitliche Komplexität der Heap-Sortierung beträgt O(n log) in allen drei Fällen (bester Fall, durchschnittlicher Fall und schlechtester Fall). Die Höhe eines vollständigen Binärbaums mit n Elementen beträgt ruhig.

2. Raumkomplexität

• Die räumliche Komplexität der Heap-Sortierung beträgt O(1).

Implementierung von Heapsort

Sehen wir uns nun die Programme der Heap-Sortierung in verschiedenen Programmiersprachen an.

Programm: Schreiben Sie ein Programm zur Implementierung der Heap-Sortierung in der Sprache C.

 #include /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int arr[], int n) { for (int i = 0; i <n; ++i) { printf('%d', arr[i]); printf(' '); } int main() a[]="{48," 10, 23, 43, 28, 26, 1}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are - 
'); printarr(a, n); heapsort(a, printf('
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-20.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C++.</p> <pre> #include using namespace std; /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int a[], int n) { for (int i = 0; i <n; ++i) { cout< <a[i]<<' '; } int main() a[]="{47," 9, 22, 42, 27, 25, 0}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are - 
'; printarr(a, n); heapsort(a, cout<<'
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-21.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C#.</p> <pre> using System; class HeapSort { /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ static void heapify(int[] a, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int[] a, int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{46," 8, 21, 41, 26, 24, -1}; int n="a.Length;" console.write('before sorting array elements are - 
'); printarr(a, n); heapsort(a, console.write('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-22.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in Java.</p> <pre> class HeapSort { /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ static void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{45," 7, 20, 40, 25, 23, -2}; n="a.length;" system.out.print('before sorting array elements are - 
'); printarr(a, n); heapsort(a, system.out.print('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-23.webp" alt="Heap Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>