자료구조 시간 때 배웠던
heap을 배열로 구현하는 문제였다.
upheap 은 구현하기 쉬우나
downheap 할 때 구현하기 헷갈렸는데
왼쪽과 오른쪽 자식이 있는데 두 개의 자식들 중 큰 것을 parent 와 바꿔주어야 한다.
이를 표현한것이 아래의 코드이다.
child = (arr[child] > arr[child + 1]) ? child : child + 1;
이것만 생각한다면 쉽게 풀 수 있는 문제였다.
#include<iostream>
#include<algorithm>
using namespace std;
int arr[100000];
int size1 = 0;
void swap(int a, int b) {
int x = arr[a];
arr[a] = arr[b];
arr[b] = x;
}
void upheap(int n) {
arr[++size1] = n;
int child = size1;
int parent = child / 2;
while (child > 1 && arr[parent] < arr[child]) {
swap(parent, child);
child = parent;
parent = child / 2;
}
}
void downheap() {
cout << arr[1] << "\n";
swap(1, size1);
size1--;
int parent = 1;
int child = parent * 2;
if (child + 1 <= size1) {
child = (arr[child] > arr[child + 1]) ? child : child + 1;
}
while (child <= size1 && arr[parent] < arr[child]) {
swap(parent, child);
parent = child;
child = child * 2;
if (child + 1 <= size1) {
child = (arr[child] > arr[child + 1]) ? child : child + 1;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
int cnt;
cin >> cnt;
while (cnt--) {
int num;
cin >> num;
if (num == 0) {
if (size1 == 0) {
cout << 0 << "\n";
}
else {
downheap();
}
}
else {
upheap(num);
}
}
}
'문제풀이 > 백준' 카테고리의 다른 글
[C++] 백준 11726번 문제풀이 (0) | 2021.02.22 |
---|---|
[C++] 백준 11724번 문제풀이 (0) | 2021.02.22 |
[C++] 백준 9095번 문제풀이 (0) | 2021.02.22 |
[C++] 백준 7662번 문제풀이 (0) | 2021.02.22 |
[C++] 백준 20546번 문제풀이 (0) | 2021.02.21 |