Implementierung eines eigenen Heaps
Angenommen, wir starten mit einem anfangs leeren Heap. Es sollen
q Abfragen ausgeführt werden. Es gibt drei Arten von Abfragen:add x– fügtxin den Heap ein
pop– entfernt das Wurzelelement (root) aus dem Heap
max– gibt das größte Element im Heap aus
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne Ganzzahl
q (1 ≤ q ≤ 10^5).Die folgenden
q Zeilen beschreiben die einzelnen Abfragen – jede Abfrage steht in einer eigenen Zeile. Es ist sichergestellt, dass bei allen add-Abfragen der Wert x den Betrag nicht überschreitet. Außerdem ist garantiert, dass alle Operationen gültig sind und keine pop-Operation auf einem leeren Heap ausgeführt wird.Ausgabe
Das Programm soll die entsprechenden Werte für alle
max-Abfragen jeweils in einer neuen Zeile ausgeben.Beispiele
Eingabe | Ausgabe |
9
add 1
add 2
max
add -3
add 4
max
add -2
pop
max | 2
4
2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB