Heap-Sort-Algorithmus
Heap Sort ist ein vergleichsbasierter Sortieralgorithmus, der eine Heap-Datenstruktur nutzt, um ein Array zu sortieren. Die Grundidee besteht darin, zunächst aus den Array-Elementen einen Heap zu erstellen und anschließend immer wieder das größte oder kleinste Element (abhängig davon, ob es sich um einen Max-Heap oder einen Min-Heap handelt) aus dem Heap zu entfernen und an das Ende des Arrays zu verschieben. Dieser Vorgang wird fortgesetzt, bis der Heap leer ist.
Ihre Aufgabe besteht darin, den Heap-Sort-Algorithmus mit einem Min-Heap zu implementieren.
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 100 000), die die Anzahl der Elemente beschreibt.Die nächste Zeile enthält
n durch Leerzeichen getrennte Ganzzahlen (), die die zu sortierenden Werte darstellen.Ausgabe
Das Programm soll das endgültig sortierte Array in aufsteigender Reihenfolge ausgeben.
Beispiele
Eingabe | Ausgabe |
7
4 3 8 -2 9 0 2 | -2 0 2 3 4 8 9 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB