![[11279번] 최대 힙](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FeOjeLp%2FbtqwWZXnCP6%2FNTJXgeZ0QiQFR7VRCrksJK%2Fimg.png)
11279번: 최대 힙
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다.
www.acmicpc.net
'힙(Heap)'이라는 자료구조를 이용하여 푸는 문제입니다.
힙은 유명한 자료구조 중 하나라고 할 수 있죠. 유용합니다.
힙(Heap)은 다른 말로 '우선순위 큐(Priority_queue)'라고도 할 수 있습니다.
그 이유는 가장 높은 value, 즉 가치가 높으면 높을수록 먼저 pop되기 때문에 그런 것입니다. (물론 가치의 기준은 MAX일수도, min일수도 있습니다.)
여기서는 MAX Heap을 구현하고 해당 function들을 이용하여 잘 돌아가는지 살펴보는 문제입니다.
우리는 이 문제를 풀기 위해 직접 Heap을 구현하고 해당 function들을 만들어줄 수 있습니다.
하지만 이러한 구조를 Heap을 쓰는 문제를 만날 때마다 적어주기에는 매우 많은 시간이 걸릴 것입니다.
그렇기 때문에 우리의 최고의 친구 C++ STL을 사용한다면 한 번에 해결할 수 있죠.
(사실 직접 구현했다가 틀린 건 비ㅁ....)
앞서 말씀드렸다싶이 Heap은 다른 말로 'priority_queue'라고 할 수 있고 이미 같은 이름을 가진 Container가 존재합니다.
저희는 이를 이용하여 단순 선언과 함께 value들의 기준을 정해주기만 하면 됩니다.
그리고 조건에 맞게 출력해주면 끝나게 되죠.