SPOJ Problem Set (main) 4119. Sortowanie przez kopcowanie Problem code: PHEAP

Proszę napisać program, który przy wykorzystaniu algorytmu sortowania przez kopcowanie, posortuje podane liczy wymierne w kolejności od najmniejszej do największej.

Wejście

W pierwszej linii wejścia znajduje się liczba testów t. Dalej kolejno w każdej z t linii umieszczono jeden test. Pierwsza liczba testu k określa liczbę liczb wymiernych do posortowania, dalej pojawiają się liczby oddzielone spacjami w postaci uproszczonych ułamków niewłaściwych a/b, gdzie a jest liczbą całkowitą a b liczbą naturalną. -100<=a<=100. Liczba b nie przekracza zakresu zmiennej typu int.

Wyjście

Dla każdego z t testów proszę wykonać następujące operacje. Proszę najpierw w liniowym czasie stworzyć kopiec i wypisać jego zawartość. Proszę kolejno zdejmować najmniejsze wartości z kopca i w osobnej linii wyświetlić zmodyfikowany kopiec. Na końcu w oddzielnej linii proszę wyświetlić posortowane wartości.

Example

Input:

4

7 1/1 69/8 51/77 56/1 70/89 -7/92 17/6

6 70/83 -11/26 -34/41 -97/75 -31/36 86/31

5 5/6 19/22 83/40 77/53 38/37

7 73/53 -36/5 -37/33 7/10 -74/77 4/3 92/93

Output:

-7/92 70/89 51/77 56/1 69/8 1/1 17/6

51/77 70/89 1/1 56/1 69/8 17/6

70/89 17/6 1/1 56/1 69/8

1/1 17/6 69/8 56/1

17/6 56/1 69/8

69/8 56/1

56/1

-7/92 51/77 70/89 1/1 17/6 69/8 56/1

-97/75 -31/36 -34/41 -11/26 70/83 86/31

-31/36 -11/26 -34/41 86/31 70/83

-34/41 -11/26 70/83 86/31

-11/26 86/31 70/83

70/83 86/31

86/31

-97/75 -31/36 -34/41 -11/26 70/83 86/31

5/6 19/22 83/40 77/53 38/37

19/22 38/37 83/40 77/53

1

38/37 77/53 83/40

77/53 83/40

83/40

5/6 19/22 38/37 77/53 83/40

-36/5 -74/77 -37/33 7/10 73/53 4/3 92/93

-37/33 -74/77 92/93 7/10 73/53 4/3

-74/77 7/10 92/93 4/3 73/53

7/10 4/3 92/93 73/53

92/93 4/3 73/53

4/3 73/53

73/53

-36/5 -37/33 -74/77 7/10 92/93 4/3 73/53

Added by:

Obszarski Paweł

Date:

2009-03-25

Time limit: 1s

Source limit:50000B

Languages: C C99 strict

2