[Algorithm/ Priority Queue(우선순위 큐)/Heap(힙) (C++)] BOJ 1927 최소힙

Priority Queue(우선순위 큐)

💡기본 Queue의 자료 구조는 FIFO(First in First out, 선입 선출)구조이다.

그에 반헤 Priority Queue는 설정된 우선순위에 따라, Top을 유지하고 먼저 Out(pop)된다.

사용 방법

queue를 import하여 사용한다.

 

[멤버 함수]

- queue에선 front를 사용해서 가장 앞에 있는 변수를 확인하는 것에 비해, priority_queue에서는 top을 활용하여 확인한다.

- push : priorityqueuq에 값을 삽입한다.

- emplace : priority queue에 구조를 삽입한다.

 

push와 emplace의 차이

push의 경우 단순히 queue에 값을 넣어준다. 다시 말하면 오브젝트로 제작후 삽입해야하므로 불필요한 복사가 많이 일어난다.

emplace의 경우 오브젝트를 생성하지 않고 바로 값을 넣는다. 즉, copy와 constructor가 합쳐진 것이라 볼 수 있다.

// 바로 값을 push한다
pqueue.emplace('a', 24); 
        
// 아래의 명령어는 오류가 난다.
pqueue.push('b', 25);     
        
// push를 사용할 때에는 pair를 만들어 준 다음에 넣어야 한다. 불필요한 복사가 일어난다.
pqueue.push(make_pair('b', 25));

 

📌내부적으로는 heap의 자료구조를 가지고 있다.

 

여기서 잠깐, Heap에 대해 알아가자!

 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

최소 힙의 정의

힙은 이진트리(Binary Tree)로 구성할 수 있으며 트리 구조체로 구현하거나 또는 1차원 배열로 쉽게 구현할 수 있다.

 

min heap(최소 힙)은 부모가 자식보다 값이 작은 힙이다. max heap은 그 반대이다.

 

이진트리의 형태를 띄고 있어 루트 노드를 1번 정점이라고 한다면, 자식 노드는 각각 2,3번 노드가 된다.

-> 여기서 부모 노드가 n이라면 왼쪽 자식의 번호는 2*n, 오른쪽 자식은 2*n +1 이다.

 

우선 순위 큐의 활용

 

우선순위 큐를 활용하기 위해서는 선언을 다음과 같이 해야한다.

#include<queue>

priority_queue<자료형, 구현체, 비교연산자> pq;

1. 자료형 : int, double 등의 기본자료형 뿐만 아니라 구조체, 클래스 등 다양하게 사용할 수 있다.
2. 구현체 : 보통 vector<자료형> 으로 구현한다. (stl에서 힙을 구현하기 좋은 자료형이면 다 가능하다고 한다. vector를 include하지 않아도 동작한다.)
3. 비교연산자 : 비교를 위한 기준을 알려준다.

위의 선언방법을 이용하여 우선순위 큐를 큰값이 아닌 작은 값으로 배치되게 하려면 비교연산자에 greater<자료형> 을 사용하면 된다. (큰수부터 출력하려면 less<자료형> 이다.)

 

문제

문제 접근

우선순위 큐에 대해서 알아보고 나니 이 문제가 쉬워보였다.

우선순위 큐에 작은 수 우선으로 삽입을 하고 0이 입력이라면, 만일 비어있다면 0을 출력하고 아니라면 가장 앞 값을 출력하면 된다.

 

정답 코드

#include <iostream>
#include <queue>

using namespace std;


int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    priority_queue<int,vector<int>,greater<int>> p;
    for(int i = 0; i<N;i++){
        int k;
        cin >> k;
        if(k == 0){
            if(p.empty()) cout<< "0"<<"\n";
            else {
                cout<< p.top()<<"\n";
                p.pop();
            }
        }else{
            p.push(k);
        }
    }
    return 0;
}