Einführung in Heap Sort in C ++
Heapsort ist eine der vergleichsbasierten Sortiertechniken und Teil der Auswahlsortierung. Wenn Sortieren als Anordnen von Datensätzen in einer bestimmten Reihenfolge unter Verwendung eines eindeutigen Werts definiert ist, der als Schlüsselelement in der angegebenen Liste bezeichnet wird. Der Begriff Sortierung wurde eingeführt, da die Benutzer die Wichtigkeit der Suche nach Elementen in einer bestimmten Menge von Informationen kennen lernten. Andernfalls wäre es sehr schwierig, nach Datensätzen zu suchen, wenn sie ungeordnet und unsortiert wären.
Es gibt viele verschiedene Techniken zum Sortieren, von denen jede ihre jeweilige Effizienz in der Zeit hat, die zum Sortieren der gegebenen Daten und des Speicherplatzbedarfs benötigt wird. Sie sind Bubble-Sort, Insert-Sort, Selection-Sort, Quick-Sort, Merge-Sort und Heap-Sort.
Was ist Heap Sort?
Heapsort ist ein Sortierungsansatz, der auf der binären Heap-Datenstruktur basiert, ähnlich der Auswahlsortierung, bei der wir zuerst den maximalen Datensatz erhalten und ihn am Ende platzieren und für den Rest der Elemente fortfahren.
Heapsort wie der Name schon sagt. Es erstellt zuerst den Heap von Datenelementen aus dem angegebenen unsortierten Array, sucht dann nach dem größten Element und platziert es am Ende des teilweise sortierten Arrays. Der Heap wird erneut aufgebaut, nach dem nächstgrößeren Datensatz gesucht und am Ende der halbsortierten Anordnung der Datensätze in den nächsten freien Steckplatz verschoben. Dieser Vorgang wird wiederholt, bis keine Objekte mehr auf dem Heap sind. Diese Technik erfordert zwei Arrays, eines zum Speichern des Heaps und das andere für ein sortiertes Array.
Algorithmus der Heap-Sortierung in C ++
- Wählen Sie zunächst root als Element mit erhöhten Rechten aus dem angegebenen Satz von Elementen aus, um einen maximalen Heap zu erstellen.
- Rekonstruieren Sie den Heap, indem Sie die Wurzel mit dem letzten Element platzieren oder austauschen.
- Die Größe des Heapspeichers wird jetzt um 1 verringert.
- Dann machen wir wieder den Heap mit den restlichen Elementen und fahren fort, bis die Heap-Größe auf 1 reduziert ist.
Beispiel für die Heap-Sortierung in C ++
Diese Technik verwendet einen binären Heap, der unter Verwendung eines vollständigen binären Baums erstellt wird, bei dem der Wurzelknoten größer als seine zwei untergeordneten Knoten ist.
Betrachten Sie das angegebene Array von Datensätzen.
Gehen wir nach dem Algorithmus vor. Es heißt, das höchste Element als Wurzel zu wählen und den maximalen Heap zu konstruieren.
1. Erste Iteration
Jetzt hat das Array die Form:
Nun hat das sortierte Array die Form:
Die Größe des Heapspeichers wird um 1 verringert, jetzt 6-1 = 5.
2. Zweite Iteration
Nun sieht der Haufen also so aus:
Das Array hat die Form:
Das sortierte Array lautet:
Die Größe des Heapspeichers wird um 1 verringert, jetzt 5-1 = 4.
3. Dritte Iteration
Der neue Haufen sieht so aus:
Das Array hat die Form:
Das sortierte Array lautet:
Die Größe des Heapspeichers wird um 1 verringert, jetzt 4-1 = 3.
4. Vierte Iteration
Der neue Haufen sieht so aus:
Das Array hat die Form:
Das sortierte Array lautet:
Die Größe des Heapspeichers wird um 1 verringert, jetzt 3-1 = 2.
5. Fünfte Iteration
Der neue Haufen sieht so aus:
Das Array hat die Form:
Das sortierte Array lautet:
Die Größe des Heapspeichers wird um 1 verringert, jetzt 2-1 = 1.
6. Letzte Iteration
Der neue Haufen sieht so aus:
Das Array hat:
4
Vom Algorithmus aus haben wir alle Schritte ausgeführt, bis die Heap-Größe 1 ist. Also haben wir jetzt das sortierte Array:
Daher ist das sortierte Array des maximalen Heaps in aufsteigender Reihenfolge. Wenn das Array in absteigender Reihenfolge sortiert werden soll, befolgen Sie die obigen Schritte mit einem minimalen Heap.
Das C ++ - Programm für die Heap-Sortierung sieht wie folgt aus:
#include
using namespace std;
void heapify(int arr(), int n, int i)
(
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;
if (largest != i) (
swap(arr(i), arr(largest));
heapify(arr, n, largest);
)
)
void heapSort(int arr(), int n)
(
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--)
(
swap(arr(0), arr(i));
heapify(arr, i, 0);
)
)
void printArray(int arr(), int n)
(
for (int i = 0; i < n; ++i)
cout << arr(i) << " ";
cout << "\n";
)
int main()
(
int arr() = ( 5, 18, 4, 13, 10, 7);
int n = sizeof(arr) / sizeof(arr(0));
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
)
Ausgabe:
Fazit
Heapsort ist die vergleichsbasierte Technik, die die Sortierung der Auswahl verbessert. Die Heap-Sortierung verwendet die Auswahl des höchsten oder niedrigsten Elements im angegebenen Array, um in aufsteigender oder absteigender Reihenfolge mit dem maximalen oder minimalen Heap zu sortieren. Führen Sie diesen Vorgang aus, bis wir eine Heap-Größe erhalten. Diese Sortiertechnik wird auch verwendet, um das größte und niedrigste Element im Array zu finden. Die Heap-Sortiertechnik ist effizienter und schneller als die Auswahlsortiertechnik.
Empfohlene Artikel
Dies ist eine Anleitung zur Heap-Sortierung in C ++. Hier diskutieren wir, was Heap-Sortierung in c ++ ist, und arbeiten mit seinem Algorithmus und Beispiel. Sie können sich auch die folgenden Artikel ansehen, um mehr zu erfahren.
- Heap-Sortierung in C
- Heap-Sortierung in Java
- Überladen in C ++
- Zeiger in C ++
- Überladen in Java