최대 힙

문제: 최대 힙 (백준 11279번)

구조 분석

해당 문제는 heap이라는 자료구조를 구현하는 문제이다. 이는 기본적인 자료구조로 c++의 stl에서 제공하는 priority_queue를 이용하면 매우 쉽게 풀 수 있다.

풀이 방법

내림차순 정렬을 위해서는 max heap을 구현해야 하며 heap sort를 실시하는데 우선 인덱스의 마지막에 새로운 노드를 삽입하고 부모 노드와 비교해서 더 큰 경우 부모 노드와 자리를 바꿔주는 식으로 동작한다. 힙 정렬을 할 때에는 n개의 요소에 대해서 힙에 삽입, 정렬을 실시해야 한다. 이떄, 힙 트리는 완전 이진 트리이므로 높이가 log(n)이다. 따라서 힙 정렬은 O(nlogn)의 시간복잡도를 갖는다.

코드

#include #include #include using namespace std;

int n; priority_queue pq;

int main() { cin.tie(NULL); cout.tie(NULL); cin » n; int x; for (int i=0; i<n; i++) { cin » x; if (x == 0) { if (pq.empty()) { cout « 0 « “\n”; } else { cout « pq.top() « “\n”; pq.pop(); } } else { pq.push(x); } } return 0; }
```

정리

stl의 priority_queue를 이용하면 힙 자료구조를 쉽게 이용할 수 있으며 이는 전체 자료정렬보다는 가장 큰 값, 또는 가장 작은 값을 구하는 데 유용하게 사용된다.