Historyjka

Skrzat WierciKoder ma problem.
Pisząc kod kopca, kopnął się w kodzie.
Pomóż mu - odrobaczyć go ;).
Stwórz kopiec, do którego będzie wrzucać po ileś elementów i wyciągać po kilka.
Po każdej informacji pokazując mu, jaki powinien być,
by porównać jego zachowanie ze swoim mógł :).

Problem

Wykonaj sekwencję komend na kopcu minimalnym, zbudowanym na pełnym drzewie binarnym (najmniejsza wartość na szczycie):

  • wstawiania elementów - która wykonuje operację wstawiania elementu do kopca dla kolejnych elementów w ciągu.

  • usuwania elementów - która wykonuje zadaną liczbę razy operację usuwania elementu z kopca.

A po wykonaniu każdej, wypisz wartości w kopcu przechodząc jego drzewo w porządku preorder.

Specyfikacja wejścia

Wejście zawiera wiersze z komendami.
(Może być zakończone pustymi wierszami, bądź nie. Znaki nowej linii będą kodowane w standardzie Linux-owym).

W każdym wierszu znajduje się: komenda wstawiania elementów albo usuwania elementów.

Komenda wstawiania elementów:

  • znak "+"

  • liczbę elementów do dodania d

  • d wartości całkowitych do wstawienia

(wszystkie elementy, liczby oddzielone pojedynczą spacją. Znak "+" nie jest poprzedzony spacją i zaczyna się od niego wiersz, po ostatniej liczbie może być spacja.).

Komenda usuwania elementów:

  • znak "-"

  • liczbę u ile razy wykonać operację usuwania elementu ze szczytu kopca.

(uwagi, jak poprzednio)

liczby do wstawienia będą liczbami całkowitymi [-231;231-1].
Natomiast d wynika z ograniczenia na maksymalną liczbę elementów, które mogą się znajdować w kopcu (opisaną w następnym punkcie).

Elementy w kopcu mogą się powtarzać !

Specyfikacja wyjścia

Po każdym wykonaniu wszystkich operacji kopcowych określonych przez każdą komendę; wypisz elementy uzyskanego kopca w porządku preorder. (Czyli wypisywania dokonujemy po wykonaniu każdej komendy).

Wypisujemy liczby całkowite, oddzielone pojedynczą spacją (po ostatniej liczbie w wierszu, ma być również pojedyncza spacja).

Limity

Obliczeniowe:
Oczekuję wykonywania operacji na kopcu w czasie O(lg n) oraz implementacji zderekursywowanej (czyli iteracyjnej).
Wypisywanie danych natomiast można wykonywać zarówno implementacją zderekursywowaną jak i rekurencyjną w czasie O(n).

Pamięciowe:
Maksymalna liczba elementów jaka może znaleźć się w kopcu to 20’000’000.
Pamięć dostępna dla programu to 400MB.
Oczekuję implementacji kopca na pełnym drzewie binarnym w implementacji tablicowej.
(Mogą, więc Państwo odgórnie zaalokować tablicę mieszczącą maksymalną liczbę elementów, by uniknąć strat np. czasu na realokacjach pamięci (no chyba, że zamortyzowanych jak w strukturze wektor)).

Kilka porad co do implementacji tablicowej struktury kopca

Poniższe porady nie są wymogiem, a tylko sugestiami w jakim kierunku można to zaimplementować.

Jeżeli zaczniemy indeksowanie pełnego drzewa binarnego (na którym budujemy kopiec) nadając korzeniowi indeks 1,
to kolejne elementy maja własność, że dzieci węzła pod indeksem i mają numery 2*i oraz 2*i+1, o ile istnieją!
Kolejna własność przy takim numerowaniu, to to że umieszczonych m elementów znajduje się w takiej tablicy na indeksach 1..m.

Ta własność pozwala na łatwe sprawdzenie, czy element istnieje (np. dziecko),
kiedy znamy ilość elementów w tak przechowywanym pełnym drzewie binarnym.

Przykład

01.in

+ 3 7 5 3
- 2
+ 4 8 9 2 4

01.out

3 7 5
7
2 4 8 7 9