-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBJAlgo_1927.java
More file actions
128 lines (112 loc) · 4.03 KB
/
Copy pathBJAlgo_1927.java
File metadata and controls
128 lines (112 loc) · 4.03 KB
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
import java.io.*;
import java.util.*;
public class BJAlgo_1927 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
MinHeap minHeap = new MinHeap();
int N = Integer.parseInt(br.readLine());
for(int i = 0; i < N; i++) {
int num = Integer.parseInt(br.readLine());
if (num == 0) {
minHeap.pop();
} else {
minHeap.insert(num);
}
}
}
}
class MinHeap {
List heap;
MinHeap() {
heap = new ArrayList<>();
heap.add(null);
}
boolean move_up(int idx) {
if (idx <= 1) {
return false;
}
int parent_idx = idx / 2;
if ((int) heap.get(idx) < (int) heap.get(parent_idx)) {
return true;
} else {
return false;
}
}
boolean move_down(int idx) {
int left_child_idx = idx * 2;
int right_child_idx = idx * 2 + 1;
// Case1: 왼쪽 자식도 없을 때
if (left_child_idx >= heap.size()) {
return false;
} else if (right_child_idx >= heap.size()) { // Case2: 오른쪽 자식만 없을 때
if ((int) heap.get(idx) > (int) heap.get(left_child_idx)) {
return true;
} else {
return false;
}
} else { // Case3: 왼쪽, 오른쪽 자식 모두 있을 때
if ((int) heap.get(left_child_idx) < (int) heap.get(right_child_idx)) {
if ((int) heap.get(idx) > (int) heap.get(left_child_idx)) {
return true;
} else {
return false;
}
} else {
if ((int) heap.get(idx) > (int) heap.get(right_child_idx)) {
return true;
} else {
return false;
}
}
}
}
void insert(int data) {
heap.add(data);
int idx = heap.size() - 1;
while (move_up(idx)) {
int parent_idx = idx / 2;
int tmp = (int) heap.get(idx);
heap.set(idx, heap.get(parent_idx));
heap.set(parent_idx, tmp);
idx = parent_idx;
}
}
void pop() {
if (heap.size() <= 1) {
System.out.println(0);
} else {
System.out.println(heap.get(1));
heap.set(1, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
int idx = 1;
while (move_down(idx)) {
int left_child_idx = idx * 2;
int right_child_idx = idx * 2 + 1;
if (right_child_idx >= heap.size()) { // Case2: 오른쪽 자식만 없을 때
if ((int) heap.get(idx) > (int) heap.get(left_child_idx)) {
int tmp = (int) heap.get(idx);
heap.set(idx, heap.get(left_child_idx));
heap.set(left_child_idx, tmp);
idx = left_child_idx;
}
} else { // Case3: 왼쪽, 오른쪽 자식 모두 있을 때
if ((int) heap.get(left_child_idx) < (int) heap.get(right_child_idx)) {
if ((int) heap.get(idx) > (int) heap.get(left_child_idx)) {
int tmp = (int) heap.get(idx);
heap.set(idx, heap.get(left_child_idx));
heap.set(left_child_idx, tmp);
idx = left_child_idx;
}
} else {
if ((int) heap.get(idx) > (int) heap.get(right_child_idx)) {
int tmp = (int) heap.get(idx);
heap.set(idx, heap.get(right_child_idx));
heap.set(right_child_idx, tmp);
idx = right_child_idx;
}
}
}
}
}
}
}