첫 시도
- 최소 힙에서 부호만 반대로 해주면 최대 힙 구현 가능
해결
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main {
public static void main(String[] ars) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
ArrayList<Integer> list = new ArrayList<>();
list.add(0);
for (int i = 0; i < N; i++) {
int a = Integer.parseInt(br.readLine());
if(a != 0){
list.add(a);
int index = list.size() - 1;
while(index > 1 && list.get(index/2) < a){
int parent = list.get(index/2);
list.set(index/2,a);
list.set(index,parent);
index /= 2;
}
}
else {
if(list.size() - 1 < 1){
sb.append(0+"\n");
}
else {
int deleteitem = list.get(1);
sb.append(deleteitem + "\n");
list.set(1, list.get(list.size() - 1));
list.remove(list.size() - 1);
int pos = 1;
while ((pos * 2) < list.size()) {
int max = list.get(pos * 2);
int maxPos = pos * 2;
if (((pos * 2 + 1) < list.size()) && max < list.get(pos * 2 + 1)) {
max = list.get(pos * 2 + 1);
maxPos = pos * 2 + 1;
}
if (max < list.get(pos))
break;
int tmp = list.get(pos);
list.set(pos, list.get(maxPos));
list.set(maxPos, tmp);
pos = maxPos;
}
}
}
}
System.out.println(sb);
}
}