알고리즘 - c++의 priority_queue 사용법
📌 c++에서 우선순위 큐 사용하기
- c++에서는 queue 헤더파일에서 priority_queue를 제공합니다.
- T에는 기본 자료형인 int, char, double 뿐만 아니라 struct, class 등이 올 수 있습니다.
- 기본적으로(default) c++의 우선순위 큐는 Max Heap으로 설정되어 있습니다. 즉, Max Heap에서는 큰 값이 우선순위가 크므로 앞에 오는 Heap으로 구성되어 있습니다. 따라서 자료형만 작성된 아래 pq는 default로 Max Heap으로 작동합니다.
1
priority_queue<T> pq;
- 또는 아래와 같이 필요한 값 3개를 전부 작성할 수도 있습니다. 여기서 Container는 벡터 같은 컨테이너를 말하고, Compare는 비교 함수입니다.
1
priority_queue<T, Container<T>, Compare> pq;
- 즉, 아래 두 개는 같은 표현입니다. 여기서 맨 마지막 인자
less<>의 경우, 내림차순 정렬하겠다는 의미가 됩니다. 즉, priority_queue는 기본적으로 Max Heap이라고 했는데, default가 less 이기 때문에 큰 값이 앞으로 오도록 작동했던 것입니다.
1
2
priority_queue<int> pq; // 자료형만 썼을 때 아래와 같은 default 값이 적용된다.
priority_queue<int, vector<int>, less<int>> pq; // less than operator 사용
- 그러면 priority_queue를 Min Heap으로 쓸 수는 없을까요? 위와는 반대로, 마지막 인자에
greater<>를 넣어 주면 오름차순 정렬하겠다는 의미가 되므로 Min Heap으로 설정할 수 있습니다. 따라서 큐에는 작은 값이 앞에 오도록 자동으로 정렬됩니다. - 이처럼 정렬 기준을 임의로 바꿔야 할 경우,
priority_queue<T> pq처럼 축약한 선언은 불가하며, 아래와 같이 필요한 값들을 전부 넣어서 선언해야 합니다.
1
priority_queue<int, vector<int>, greater<int>> pq; // greater than operator 사용
- 우선순위 큐에 pair가 들어가게 작성해야 할 경우가 있다면 다음과 같이 작성할 수 있습니다. T에
pair<int, int>가 들어가는 것 뿐입니다. - 아래와 같이 선언하면, pair에서 first 값을 기준으로 Max-Heap 동작을 합니다.
1
priority_queue<pair<int, int>> pq;
- 만약 pair<int, int> 형을 우선순위 큐에서 사용하고 싶은데, Min-Heap으로 동작하게 하려면 똑같은 방법으로 아래와 같이 작성합니다.
1
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
- [참고] C++14 버전 이후에는 자료형 추론이 가능해서, 마지막 operator 를
greater<>와 같이 자료형을 명시해서 적어주지 않아도 컴파일이 가능합니다. 하지만 여러 코딩 테스트 등 다양한 환경에서 모두 C++14 이후를 보장할 수는 없으므로 안전하게 자료형을 명시해 주는 것이 좋습니다.