[백준/C++] 1927번 최소 힙

문제: www.acmicpc.net/problem/1927

1927번: 최소 힙

 

 

문제풀이

 

최소 힙의 구현 문제이다.

 

C++ STL을 이용하면 쉽게 풀 수 있다.

 

코드(직접 구현)

#include <iostream>

using namespace std;

int rear=0;
int arr[100005];

void push(int);
void pop();
bool empty();

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int N;
    cin>>N;

    for(int i=0; i<N; i++){
        int x;
        cin>>x;

        if(x != 0){
            push(x);
        }
        else{
            pop();
        }
    }

    return 0;
}

void push(int x){
    arr[++rear] = x;
    int child = rear;
    int parent = child/2;

    while(parent > 0 && arr[parent] > arr[child]){
        swap(arr[parent], arr[child]);
        child = parent;
        parent = child/2;
    }
}

void pop(){
    if(empty()){
        cout<<0<<"\n";
        return;
    }

    cout<<arr[1]<<"\n";
    arr[1] = arr[rear];
    rear--;
    int parent = 1;
    int child = parent*2;
    if(child+1 <= rear){
        child = (arr[child] < arr[child+1]) ? child:child+1;
    }

    while(child <= rear && arr[parent] > arr[child]){
        swap(arr[parent], arr[child]);

        parent = child;
        child = child*2;
        if(child+1 <= rear){
            child = (arr[child] < arr[child+1]) ? child:child+1;
        }
    }
}

bool empty(){
    if(rear == 0){
        return true;
    }
    else{
        return false;
    }
}

 

코드(C++ STL)

#include <iostream>
#include <queue>

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int N;
    cin>>N;

    priority_queue<int, vector<int>, greater<int>> pq; //우선순위 큐(오름차순)
    for(int i=0; i<N; i++){
        int x;
        cin>>x;

        if(x != 0){ //입력값이 0이 아니면 push
            pq.push(x);
        }
        else{ //입력값이 0이고
            if(!pq.empty()){ //큐가 비어있지 않다면 pop
                cout<<pq.top()<<"\n";
                pq.pop();
            }
            else{ //큐가 비어있다면 0 출력
                cout<<0<<"\n";
            }
        }
    }

    return 0;
}

 

 

결과