TIL (2022.04.05)

Heap

heap은 빠르게 최댓값, 최솟값을 찾아내기 위한 자료구조이며, 완전 이진트리 (complete binary tree)를 기본으로 한다.

max-heap, min-heap을 사용하면 특정 숫자가 추가되고 삭제 되었을 때 -> 최대 최소 구할 시 시간은 O(logn)

max-heap =
루드 노드에는 전체 숫자 중 최댓값이 항상 들어가는 것
-> 삭제는 루트 노드에서만 가능
-> 몇번째 최댓값 구하는 것 불가능

min-heap =
루트 노드에는 전체 숫자 중 최솟값이 항상 들어가는 것

[백준 11279번 최대 힙] c++(https://www.acmicpc.net/problem/11279)

priority_queue를 사용하면 풀 수 있다. 큰 값이 우선순위로 나옴.

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

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    priority_queue<long long> pq;
    int n;
    cin>>n;

    for(int i=0;i<n;i++){
        int num;
        cin>>num;
        if(num==0){
            if(pq.empty()){
                cout<<0<<'\n';
            }else{
                int tp=pq.top();
                cout<<tp<<'\n';
                pq.pop();
            }
        }else{
            pq.push(num);
        }
    }
    return 0;
}

[백준 1927 최소 힙]c++(https://www.acmicpc.net/problem/1927)
priority_queue를 반대로 하면 최소 힙이 된다.
priority_queue<int,vector< int>,greater< int>> pq;
= int 형을 vector에 담고 작은 순서대로

greater 를 위해서 #include < functional > 해야한다.

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;

    priority_queue<int,vector<int>,greater<int>> pq;
    for(int i=0;i<n;i++){
        int num;
        cin>>num;
        if(num==0){
            if(pq.empty()){
                cout<<0<<'\n';
            }else{
                cout<<pq.top()<<'\n';
                pq.pop();
            }
        }else{
            pq.push(num);
        }
    }
}