74. 최소힙 [우선순위 큐 이용]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

5

3

6

0

5

0

2

4

0

-1

 

출력예제 1

3

5

2

 

풀이 

- PriorityQueue는 기본적으로 최대힙 구조를 지원

=> 최소힙으로 만들려면 어떤 방식을 사용해야하는지가 중요함

- 6>5이지만 -를 붙이면 -6<-5가 된다.

=> 이를 이용해 큐에 넣을때 -로 푸쉬하고 출력할때 -를 붙여서 출력하면 원래값을 얻을 수 있다.

 

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

//74. 최소힙 (우선순위 큐)
//부모노드의 값이 왼쪽 자식과 오른쪽 자식보다 작아야함 => 가장작은 값이 루트에 들어감
// -5는 -6보다 큼 => 최대힙 구조로 -5가 루트, -6이 자식이 됨 => 최소힙 구현 시 -를 +로 바꿔서 출력
int main(){
    int a;
    priority_queue<int> pQ;

    while(true){
        scanf("%d", &a);
        if(a==-1) break;
        if(a==0) {
            if(pQ.empty()) printf("-1\n");
            else{
                printf("%d\n", -pQ.top());
                pQ.pop();
            }
        }
        else pQ.push(-a);
    }

    return 0;
}