最大ヒープでは、すべての親の値が子の値以上であるため、最大値は常に根にある。値を挿入するときは配列の末尾に追加し、親より大きい間、上へ移動させる。最大値を削除するときは最後の値を根に移し、より大きい子と交換しながら下へ移動させる。各操作で根から葉までの経路をたどるのは最大一度なので、挿入と削除の時間計算量はそれぞれO(log N)である。プリミティブ型の配列を使うため、空間計算量はO(N)であり、配列の容量は挿入コマンドの最大数に合わせる。
入力は空白区切りのトークンとして読み取り、結果はStringBuilderにまとめて出力する。空のヒープから削除しようとした場合は、問題の仕様どおり0を出力する。
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static BufferedReader reader =
new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer tokenizer;
private static int nextInt() throws IOException {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return Integer.parseInt(tokenizer.nextToken());
}
public static void main(String[] args) throws IOException {
int n = nextInt();
int[] heap = new int[n + 1];
int size = 0;
StringBuilder output = new StringBuilder();
for (int i = 0; i < n; i++) {
int value = nextInt();
if (value == 0) {
if (size == 0) {
output.append(0).append('\n');
} else {
output.append(heap[1]).append('\n');
heap[1] = heap[size--];
int parent = 1;
while (parent * 2 <= size) {
int child = parent * 2;
if (child + 1 <= size && heap[child + 1] > heap[child]) {
child++;
}
if (heap[parent] >= heap[child]) {
break;
}
int temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;
parent = child;
}
}
} else {
int child = ++size;
while (child > 1 && heap[child / 2] < value) {
heap[child] = heap[child / 2];
child /= 2;
}
heap[child] = value;
}
}
System.out.print(output);
}
}