[백준/C++] 1927번: 최소 힙 - priority_queue의 내부 구조 파헤치기

 

 

 

1. 문제 정보

• 문제 번호: 1927번
• 문제 이름: 최소 힙
• 문제 요약: 최소 힙을 이용하여 다음 연산을 지원하는 프로그램을 작성하라.
  1. 배열에 자연수 x를 넣는다.
  2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

최소 힙 모양

최소 힙은 작은게 위에 있는 트리 구조 이다. 

 

 

2. 핵심 개념: Priority Queue와 내부 컨테이너

C++ STL에서 제공하는 priority_queue는 이름은 큐(Queue)지만, 실제로는 힙(Heap) 자료구조로 동작합니다. 여기서 재밌는 점은 이 녀석이 데이터를 담기 위해 내부적으로 다른 컨테이너를 빌려 쓴다는 것입니다.

 

왜 내부 컨테이너로 vector를 쓸까?

우선순위 큐를 선언할 때 보통 priority_queue<int, vector<int>, greater<int>>와 같이 작성합니다. 여기서 vector<int>가 바로 내부 컨테이너입니다.

1. 힙 유지의 효율성: 힙은 완전 이진 트리 구조입니다. 배열(또는 벡터) 기반으로 트리 노드를 관리하면 부모 노드의 인덱스가 i일 때 자식은 2i와 2i+1이라는 단순한 수식으로 접근이 가능합니다. 포인터를 사용하는 것보다 훨씬 빠르죠.
2. 동적 메모리 관리: 데이터가 얼마나 들어올지 모르는 상황에서 vector는 스스로 크기를 조절하며 메모리를 효율적으로 관리합니다.
3. 랜덤 액세스: 힙 구조를 유지하기 위해 노드 간 위치를 바꿀 때 인덱스로 즉시 접근할 수 있는 vector의 특성이 매우 유리합니다.

 

3. 코드 구현 (최소 힙 설정)

기본적으로 C++의 priority_queue는 최대 힙(Max Heap)으로 동작합니다. 따라서 최소 힙(Min Heap)으로 바꾸기 위해서는 세 번째 인자에 비교 연산자인 greater<int>를 명시해줘야 합니다.

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    // 입출력 최적화 (데이터가 많으므로 필수!)
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    // 최소 힙 선언: <데이터 타입, 내부 컨테이너, 비교함수>
    priority_queue<int, vector<int>, greater<int>> pQ;

    while(N--) {
        int num;
        cin >> num;

        if (num > 0) {
            // 자연수라면 힙에 삽입
            pQ.push(num);
        } 
        else if (num == 0) {
            // 0이라면 최솟값 출력 후 제거
            if (pQ.empty()) {
                cout << 0 << "\n";
            } 
            else {
                cout << pQ.top() << "\n";
                pQ.pop();
            }
        }
    }

    return 0;
}

---

4. 배운 점 & 회고 (TIL) ✍️

① 우선순위 큐의 세 가지 인자

priority_queue의 템플릿 인자를 다시 한번 복습했습니다.

• Type: 데이터 형식
• Container: 데이터를 저장할 구조 (기본값 vector<Type>)
• Compare: 우선순위 판단 기준 (기본값 less<Type> - 내림차순/최대 힙)

② 시간 복잡도의 이점

일반적인 배열에서 최솟값을 찾고 지우려면 $O(N)$이 걸리지만, 힙을 사용하면 삽입과 삭제 모두 O(log N)에 해결됩니다. 이번 문제처럼 N이 10만 개일 때, 전체 연산은 약 100,000 \times \log(100,000)정도로 매우 가뿐하게 통과할 수 있습니다.

③ 왜 큐인데 top()인가?

일반적인 queue는 front()를 쓰지만, priority_queue는 가장 우선순위가 높은(힙의 루트 노드) 데이터를 보기 때문에 top()을 사용합니다. stack과 명칭이 같아 헷갈릴 수 있으니 주의해야겠네요!