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