c++ priority_queue

1. 우선순위 큐 = 힙

    priority_queue<int> pq;
    priority_queue<int, vector<int>, less<int>> l_pq;
    priority_queue<int, vector<int>, greater<int>> g_pq;

    for (int i = 0; i < 4; i++) { // 0 1 2 3
        pq.push(i);
        l_pq.push(i);
        g_pq.push(i);
    }

    while (pq.size()) { // 3 2 1 0
        cout << pq.top();
        pq.pop();
    }

    while (l_pq.size()) { // 3 2 1 0
        cout << l_pq.top();
        l_pq.pop();
    }

    while (g_pq.size()) { // 0 1 2 3
        cout << g_pq.top();
        g_pq.pop();
    }

pair 사용시 first의 우선순위를 먼저 보고 같다면 second를 본다.

 

 

2. 구조체를 사용한 우선순위 큐

struct node {
    int x, y;
};

struct compare {
    bool operator()(node& a, node& b) {
        return a.x < b.x;
    }
};

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

    priority_queue<node, vector<node>, compare> pq;

    for (int i = 0; i < 4; i++) pq.push({ i,0 }); // {0,0} {1,0} {2,0} {3,0}

    while (pq.size()) {
        node it = pq.top();
        pq.pop();
        cout << it.x << ' ' << it.y << '\n'; // {3,0} {2,0} {1,0} {0,0}
    }
    
    return 0;
}

operator로 우선순위를 정해줄 수 있다.

sort에서 compare을 만들때와 반대로 a<b 이면 큰 값이 우선순위를 가지고 a>b이면 작은 값이 우선순위를 가진다.

bool compare(int a, int b) {
    return a > b;
}

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

    vector<int> ar(4);
    for (int i = 0; i < 4; i++) ar[i] = i; // 0 1 2 3
    sort(ar.begin(), ar.end(), compare);

    for (int it : ar) cout << it << ' '; // 3 2 1 0
    return 0;
}