Den Heap korrigieren
Angenommen, es liegt ein Max-Heap mit
n Zahlen vor, bei dem alle Elemente die Max-Heap-Eigenschaft erfüllen – mit Ausnahme der Wurzel. Die Aufgabe besteht darin, diesen Heap so anzupassen, dass schließlich alle Elemente tatsächlich die Max-Heap-Eigenschaft einhalten.Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 100 000).In der nächsten Zeile stehen
n durch Leerzeichen getrennte ganze Zahlen (), die die Werte der Heap-Elemente darstellen.Ausgabe
Das Programm sollte
n durch Leerzeichen getrennte ganze Zahlen ausgeben, die den korrigierten Heap beschreiben.Beispiele
Eingabe | Ausgabe |
7
-1 9 7 1 3 6 5 | 9 5 7 1 -1 6 3 |
8
-2 7 5 2 1 3 4 1 | 7 2 5 1 1 3 4 -2 |
Erklärung
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB