Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HEAP - Kopiec

Zadanie polega na zaimplementowaniu kopca min-heap przechowującego liczby całkowite z zakresu [-109..109]. Należy zaimplementować operacje budowy kopca z dowolnej tablicy liczb oraz operację ekstrakcji najmniejszego elementu (wierzchołka kopca).

W funkcji heapify, w przypadku gdy obaj synowie mają równą wartość należy wybrać lewego syna.

Wejście

W pierwszym wierszu podana jest liczba testów. Dalej znajdują się kolejne testy.

Dla każdego testu wpierw podana jest liczba n, a następnie n liczb na podstawie których należy zbudować kopiec (liczby należy wczytać do tablicy i używając funkcji BuildHeap utworzyć kopiec). W kolejnym wierszu znajduje się liczba m i kolejno m wierszy zawierających jedną literę E lub P.

Wyjście

Dla każdej instrukcji E lub P należy wypisać w jednym wierszu:

  • Dla każdej litery P należy wypisać aktualny stan kopca (wypisać zawartość tablicy, oddzielając kolejne liczby spacjami).
  • Dla każdej litery E należy wykonać ekstrakcję elementu najmniejszego, tzn. wypisać element najmniejszy i usunąć z kopca (z zachowaniem własności kopca).

Przykład

Wejście:
2
10
3
-14
-3
15
13
-5
6
-8
-11
1

6
P
E
E
P
E
E

10
-18
7
-10
-1
-17
-14
0
6
-8
-4

6
P
E
E
P
E
E


Wyjście:
-14 -11 -5 -8 1 -3 6 3 15 13
-14
-11
-8 1 -5 3 15 -3 6 13
-8
-5
-18 -17 -14 -8 -4 -10 0 6 -1 7
-18
-17
-14 -8 -10 -1 -4 7 0 6
-14
-10



Dodane przez:Adam Nadolski
Data dodania:2007-03-17
Limit czasu wykonania programu:1s-2s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET

ukryj komentarze
2012-05-21 17:54:05 Karol Kurek
@Marcin Skiba
Zarówno Rafał Kostro jak i Piotr Kąkol napisali poprawny kopiec w dół, a w zadaniu jest nie uwzględnione, że synów należy "segregować". Link jaki podał Piotr Kąkol jest ważny by się nie złapać w pułapkę :)
2012-01-09 12:42:48 Marcin Skiba
Kopiec z gotowej tablicy można zbudować 'w górę' albo 'w dół'. W zadaniu wymagana jest podejście 'w dół'. Tyle w temacie ;)
2010-02-13 11:05:07 Piotr KÄ…kol
Też nie wiedziałem, czemu taki jest wynik, więc zapytałem na forum i dostałem wyjaśnienie:
http://www.coderscity.net/ftopic30575.html
PS Jednak mocno nie polecam forum coderscity ze względu na moderatorów, którzy znacznie utrudniają znalezienie odpowiedzi na dane pytanie, choć w powyższym wątku tego nie widać (np. gdy uważają, że pytanie autora jest mało ważne to je usuwają). Chyba, że ktoś potrzebuje szybkiej odpowiedzi i jest przygotowany na nerwy i utrudnienia.
2010-02-12 18:32:42 Rafa³ Kostro
mam wrażenie że przykład jest błędny, jeśli wrzucamy na kopiec 3 -14 -3 15 13 -5 6 -8 -11 1 to jakbym na kartce nierozpisywał to kopiec będzie wyglądał tak: -14 -11 -5 -8 1 -3 6 15 3 13 natomiast w przykładzie przy wypisaniu kopca (pierwsze P) jest: -14 -11 -5 -8 1 -3 6 3 15 13 a więc zamienione jest 3 i 15.

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.