139p 우선순위큐 커스텀 정렬

작성한 질문수 11

1

안녕하세요 sunny님 ㅎㅎ

우선순위큐 커스텀 정렬을 넣을 때 반대로 넣어야 하는 특징이있다고 적혀있습니다.

>>

C++의 우선순위큐는 최대 힙(max heap)을 기본으로 구현이 되어있으며 가장 큰 요소가 가장 위에 정렬되게 설정이 되어있습니다.

즉, 다음과 같이 했을 때 기본적으로 내림차순 정렬이 되는 것이죠. 

priority_queue<int> pq2; // 내림차순

이와 동일하게 < 오퍼레이터에 맞게  x < a.x 로 설정하게 되면 우선순위큐의 가장 맨 위에 가장 큰 요소가 오게 됩니다. 즉, {1, 2, 3}을 넣었을 때 3이 가장 위에 올라오게 되는 것이죠.

보통 vector에서 정렬 할 때 x < a.x 이런 식으로 정렬하게 되면 {1, 2, 3}으로 정렬되고 앞의 요소는 1인데 이와는 반대인 셈이 된다고 생각하면 됩니다.

그렇기 때문에 가장 작은 값을 우선순위 큐 맨 위에서 뽑게 하려면 x > a.x 이런식으로 정의해야 {3, 2, 1} 이런식으로 정렬되기 때문에 반대로 설정해야 합니다.  

반대로, 우선순위 큐가 아닐 때에는 어떤 원리인지도 궁금합니다. 감사합니다

>>

이 때는 반대가 아닌 그대로 내림차순이면 -> >, 오름차순이면 < 이런식으로 compare 함수를 정의해서 정렬하면 됩니다.

대표적으로 map이 있습니다. map의 경우 원래는 키가 오름차순 정렬되는데요.

이를 바꾸려면 다음과 같이 하면 됩니다.

#include <bits/stdc++.h>

struct Point {
    int y, x;
    Point(int y, int x) : y(y), x(x) {}
};

struct customCompare {
    bool operator()(const Point& a, const Point& b) const {
        return a.x > b.x; // x 값을 기준으로 내림차순 정렬
    }
};

int main() {
    std::map<Point, int, customCompare> points;
    points[Point(1, 2)] = 1;
    points[Point(3, 4)] = 2;
    points[Point(5, 6)] = 3;
    points[Point(7, 8)] = 4;
    
    for (const auto& entry : points) {
        std::cout << "(" << entry.first.y << ", " << entry.first.x << ") : " << entry.second << "\n";
    }
    
    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.