BOJ 11279 - 최대 힙(C++) + Heap 개념정리 / Team Fortune Drill Week1

https://www.acmicpc.net/problem/11279

최초 풀이: 2024. 02. 09

재풀이: 2025. 04. 11

#data_structures #priority_queue

내 풀이(최초)

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

void Insert(vector<int> &Heap, int x);
void DeleteMax(vector<int> &Heap);
void SiftDown(vector<int> &Heap, int k);

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, num;
    vector<int> v;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> num;
        if(num == 0){
            if(v.size() == 0)
             cout << 0 << '\n';
            else{
                cout << v[0] << '\n';
                DeleteMax(v);
            }
        }
        else{
            Insert(v, num);
        }
    }
    return 0;
}

void Insert(vector<int> &Heap, int x){
    int n = Heap.size();
    int parent;
    Heap.push_back(x);
    n += 1;
    for(int k = n-1 ; k > 0; k = parent){
        parent = int((k - 1) / 2);
        if(Heap[parent] >= Heap[k])
         return;
        else
         swap(Heap[parent], Heap[k]);
    }
}

void DeleteMax(vector<int> &Heap){
    Heap[0] = Heap.back();
    Heap.pop_back();
    SiftDown(Heap, 0);
}

void SiftDown(vector<int> &Heap, int k){
    int n = Heap.size();
    while(2 * k + 1 < n) {
        int j;
        if((2 * k + 2) == n || Heap[k * 2 + 1] > Heap[k * 2 + 2])
         j = k * 2 + 1;
        else
         j = k * 2 + 2;
        if(Heap[k] >= Heap[j])
         return;
        swap(Heap[k], Heap[j]);
        k = j;
    }
}

내 풀이(두 번째)

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

priority_queue<int> MaxHeap;

void Insert(int x);
void DeleteMax();

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, x;
    cin >> N;
    
    for(int i = 0; i < N; i++){
        cin >> x;
        if(x == 0) DeleteMax();
        else Insert(x);
    }
    
    return 0;
}

void Insert(int x){
    MaxHeap.push(x);
}

void DeleteMax(){
    if(MaxHeap.empty()) cout << 0 << '\n';
    else {
        cout << MaxHeap.top() << '\n';
        MaxHeap.pop();
    }
}

💡 Heap(힙)이란?

힙은 “특정한 정렬 조건”을 만족하는 완전 이진트리(Complete Binary Tree) 구조

• MaxHeap : 부모 노드 ≥ 자식 노드 (가장 큰 값이 루트)
• MinHeap : 부모 노드 ≤ 자식 노드 (가장 작은 값이 루트)

시간복잡도

• 삽입: O(log N)
• 삭제: O(log N)
• 최댓값 접근: O(1)

🛠️ C++에서는 priority_queue로 사용 가능

• priority_queue<int>는 기본적으로 Max Heap임
• priority_queue<int, vector<int>, greater<int>>를 쓰면 Min Heap

참고) priority_queue<자료형, 컨테이너, 비교함수>

인자 순서	의미
1번째	자료형 (예: int)
2번째	내부에서 사용하는 컨테이너 (기본값: vector<자료형>)
3번째	우선순위를 정하는 비교 함수 객체 (비교자)