구조체 우선순위 큐

구조체(struct) 같은 자료구조를 넣어서 우선순위 큐를 만들 수 있습니다.

구조체를 일단 만들어보죠.

 

#include <iostream>
#include <queue>

using namespace std;

struct Point
{
    int y, x;
    Point(int _y, int _x) : y(_y), x(_x) {}
    Point() { y = -1; x = -1; }
    
    bool operator < (const Point& a) const
    {
        return x > a.x;
    }
};

int main()
{
    priority_queue<Point> pq;
    
    for (int i = 1; i <= 6; ++i)
    {
        pq.push({i, i});
    }
    
    cout << pa.top().x << '\n';
}

 

이 결과값의 맨 위는 1입니다.

분명 operator는 >로 결과값을 반환해서 내림차순으로 되어야 하지 않나요?

하는데

이게 특징입니다.

우선순위 큐에 커스텀 정렬을 넣을 때는 반대로 넣어야 합니다.

> = 오름차순

< = 내림차순

 

그렇다면 반대의 결과는 어떨까요?

#include <iostream>
#include <queue>

using namespace std;

struct Point
{
    int y, x;
    Point(int _y, int _x) : y(_y), x(_x) {}
    Point() { y = -1; x = -1; }
    
    bool operator < (const Point& a) const
    {
        return x < a.x;
    }
};

int main()
{
    priority_queue<Point> pq;
    
    for (int i = 1; i <= 6; ++i)
    {
        pq.push({i, i});
    }
    
    cout << pa.top().x << '\n';
}

최대가 나오네요.

그래서 가장 최소를 끄집어 내려면 >

최대면 <

기본 정렬과 반대라고 생각하면 된다!!!

 

물론 이렇게도 가능

#include <iostream>
#include <queue>

using namespace std;

struct Point
{
    int y, x;
};

struct Compare
{
    bool operator()(Point a, Point b)
    {
        return a.x < b.x
    }
};

int main()
{
    priority_queue<Point, vector<Point>, Compare> pq;
    
    for (int i = 1; i <= 6; ++i)
    {
        pq.push({i, i});
    }
    
    cout << pq.top().x << '\n';
    
    return 0;
}

 

이런식으로 Point라는 타입의 요소를 저장하는 우선 순위 큐를 선언이 되고,

Compare라는 구조체를 사용해서 요소를 정렬하는 우선 순위 큐입니다.

vector<Point>라는 것은 큐의 내부 컨테이너로 사용이 됩니다.

 

아우 피곤해라 끄으읕