[BOJ알고리즘, C++]#1927_최소 힙, 힙, 우선순위 큐

 

[BOJ알고리즘, C++]#1927_최소 힙

 

BOJ 알고리즘 문제 풀이, 1927번 문제 "최소 힙"

C++의 STL이 제공하는 priority_queue 컨테이너를 활용하는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

#2. 풀이

1. 힙

[자료구조]#5_트리

 

• [정의] : 힙은 반 정렬 상태를 유지하는 이진트리의 한 종류입니다. 힙은 두 종류로, 최대 힙은 부모 노드가 자식 노드보다 크거나 같고, 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 형태를 유지합니다.

 

2. 우선순위 큐

[자료구조]#7_우선순위 큐

 

• [개념] : 우선순위 큐는 원소들이 우선순위에 따라 정렬된 연결 자료구조입니다. 원소의 삽입/삭제 순서와 무관하게 가장 높은 우선순위를 가진 원소가 먼저 제거되는 특징을 갖고 있습니다. 우선순위 큐는 삽입/제거 작업 시 정렬 작업을 자동적으로 수행합니다. 결과적으로, 우선순위 큐는 내부적으로 항상 정렬된 상태를 유지하는 자료구조입니다.
• [성능] : 우선순위 큐의 삽입/삭제 작업의 평균/최악 시간 복잡도는 O(log n)입니다. 이유는 간단합니다. 우선순위 큐의 삽입/삭제 작업은 매번 정렬 작업을 동반하며, 힙의 정렬 작업에 소요되는 시간이 일반적으로 O(log n) 시간 복잡도를 갖기 때문입니다.
• [단점] : 우선순위 큐는 삽입/삭제 작업 시 매번 정렬 작업을 수행합니다. 따라서, 정렬 작업에 추가적인 메모리 공간이 필요하며, 그 구현이 비교적 복잡합니다. 

 

3. priority_queue 컨테이너

[Basic C++] #69_priority_queue

 

4. priority_queue의 정렬 기준

1. priority_queue는 선언 시 세번 째 인자를 통해 그 정렬 기준을 변경할 수 있습니다. 디폴트 설정은 "최대 힙(less)"이며, "최소 힙(greater)" 선언을 위해선 별도의 사용자 정의 비교 함수를 세 번째 인자로 전달해야 합니다.
2. 간단합니다. 기본 정렬 기준은 "최대 힙(less)"이며, "최소 힙(greater)"으로 변경하거나 별도의 정렬 기준을 활용하기 위해선 구조체 오버로딩, 람다 함수, 그리고 함수 객체 등을 별도로 정의하면 됩니다. 
3. 주의할 점은 "less(<)"는 보다 작은 값이 우선순위가 높은 것이 아니라, 우항 즉 보다 큰 값이 우선순위가 높도록 설정합니다. 결과적으로, "greater(>) 는 최소 힙", 그리고 "less(<)는 최대 힙"으로 기억하면 됩니다.

 

#3. 코드

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int N;
    // # 정렬 기준 변경, greater(>)는 "최소 힙" 선언
    priority_queue<int, vector<int>, greater<int>> pq;
    
    cin >> N;
    while(N--)
    {
        int tmp;
        cin >> tmp;
        
        if(tmp != 0)
        {
            pq.push(tmp);
        }
        else
        {
            if(!pq.empty())
            {
                cout << pq.top() << '\n';
                pq.pop();
            }
            else
            {
                cout << 0 << '\n';
            }
        }
    }
    
    return 0;
}