[C++] Priority_queue

https://en.cppreference.com/w/cpp/container/priority_queue

std::priority_queue - cppreference.com

 

 

stack이 후입선출, queue가 선입선출로 데이터를 관리하고, priority_queue는 우선순위를 정하여 해당 우선순위에 맞게 데이터를 관리한다.

기본적으로는 std::less<type>, 즉 값이 작아지도록 정렬되게(내림차순) 지정되어 있으며, 이 우선 순위를 원하는 데로 조종 가능하다.

 

 

 

---

 

1. 기본 priority queue.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue <int> pq;

    pq.push(4);
    pq.push(7);
    pq.push(7);
    pq.push(1);

    cout << "------------------" << endl;
    for (; pq.empty() == false; pq.pop()) {
        auto data = pq.top();
        cout << data << endl;
    }
    cout << "-------------------";

    
    return 0;
}

 

 

2. std 지원 기능을 가지고 우선순위 변경

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue <int, vector<int>, greater<int>> pq;

    pq.push(4);
    pq.push(7);
    pq.push(7);
    pq.push(1);

    cout << "------------------" << endl;
    for (; pq.empty() == false; pq.pop()) {
        auto data = pq.top();
        cout << data << endl;
    }
    cout << "-------------------";

    
    return 0;
}

 

 

이렇게 priority_queue를 생성 할 때 마지막 template class에 greater / less를 지정함으로써 내림차순으로 되어 있는 priority_queue를 오름차순으로 변경 가능하다.

 

 

중간에 vector는 해당 queue를 어떤 container에서 보관할거냐 물어보는 건데.. 

https://en.cppreference.com/w/cpp/named_req/SequenceContainer

이 기준을 만족, 즉 위에서 정의해 둔 함수를 모두 가지고 있는 container가 오면 된다고 한다.

 

다만, 걍 무지성으로 vector 써도 큰 문제는 없을 듯 하다.

---

 

 

 

 

3. 원하는 데이터를 넣고, 원하는 방식으로 우선순위 변경

#include <iostream>
#include <queue>

using namespace std;

class myClass {
public:
    int data_x;
    int data_y;
    myClass(int x, int y) : data_x(x), data_y(y) {}
};

int main() {
    auto cmpFunc = [](myClass A, myClass B) {
        if (A.data_x < B.data_x) return true;
        else if (A.data_x == B.data_x && A.data_y < B.data_y) return true;
        else return false;
    };

    priority_queue <myClass, vector<myClass>, decltype(cmpFunc)> pq(cmpFunc);

    pq.push(myClass(4,1));
    pq.push(myClass(7,2));
    pq.push(myClass(7,6));
    pq.push(myClass(1,3));

    cout << "------------------" << endl;
    for (; pq.empty() == false; pq.pop()) {
        auto data = pq.top();
        cout << data.data_x << ' ' << data.data_y << ' ' << endl;
    }
    cout << "\n-------------------";

    
    return 0;
}

 

 

결국 이 형태를 많이 쓰게 되지 않을까 싶다.

 

실제 코딩테스트에서도 x,y 좌표를 가지고 정렬해야 할 일이 생긴다거나, 두 개의 값을 이렇게 저렇게 비교하여 줄을 세워야 할 경우가 많을 것이다.

 

 

    auto cmpFunc = [](myClass A, myClass B) {
        if (A.data_x < B.data_x) return true;
        else if (A.data_x == B.data_x && A.data_y < B.data_y) return true;
        else return false;
    };

    priority_queue <myClass, vector<myClass>, decltype(cmpFunc)> pq(cmpFunc);

 

결국 '어떤 기준으로 줄을 세울까' 를 결정하는 함수를 정하는게 제일 중요하다.

여기선 람다 함수를 이용하여 해당 compare function을 정해 주었다.

그리고 compare function 만들 때 아래의 두 가지를 지켜서 만들어주자.

 

 

1. 같은 data type으로 두 개의 parameter를 받는다.

2. bool 형태의 return 값을 가져야 한다.

 

1번 조건은, priority_queue 내부에서 [두 개의 elem을 비교] 하여 줄 세울 때 사용되고

2번 조건은, priority_queue 내부에서 두 개의 elem을 [비교 하여 줄 세울 때] 사용된다.

 

 

A, B 이렇게 두 개를 비교할 때,

 

return true이면 A와 B의 자리를 바꾸고,

return false이면 A와 B의 자리를 바꾸지 않는다.

 

 

이 부분을 생각하고 구현하면 쉽게 구현이 가능하다.

사실.. 헷갈리면 그냥 구현 해 보고, 한번 출력하면 맘 편하게 확인 가능하긴 하다.

반대면 부등호 변경하면 되지 뭘.