[C++] STL priority_queue 정리

요구 사항

• 헤더 : <queue>
• 네임스페이스 : std

멤버 함수

• empty : priority_queue가 비어 있는지를 테스트
• pop : priority_queue의 우선순위가 가장 높은 요소를 최상위 위치에서 제거
• push : 우선순위에 따라 요소를 priority_queue에 추가
• emplace : 요소를 구성하고 우선순위에 따라 priority_queue에 추가
• size : priority_queue에 있는 요소 수를 반환
• top : priority_queue의 최상위 위치에 있는 요소에 대한 참조를 반환
• swap : 두 개의 priority_Queue의 내용을 바꿈

활용

#include <queue>

priority_queue<Type, Container, Compare> pq;

 

매개 변수

Type

priority_queue에 저장되는 요소 데이터 형식

 

Container (Optional)

priority_queue를 구현하는 데 사용되는 기본 컨테이너의 형식

 

Compare (Optional)

두 요소 값을 정렬하기 위한 기준

기본값은 내림차순 less<type>

custom comparator

• 비교 함수를 bool를 리턴하는 함수가 아닌 () 연산자를 오버라이딩 하는 방식으로 정의해야 한다
• priority_queue의 top 원소는 container의 back에 있기 때문에 정렬할 때 조건의 부호를 잘 확인해야 한다

구조체를 활용하여 비교 함수 정의

#include <iostream>
#include <queue>

using namespace std;

struct cmp {
  bool operator()(int a, int b){
    // 내림차순 정렬
    return a < b; 
  }
};

int main(){
  priority_queue<int, vector<int>, cmp> pq;
  
  pq.push(3);
  pq.push(1);
  pq.push(4);

  // output: 4 3 1
  while(!pq.empty()){
    cout << pq.top() << " ";
    pq.pop();
  }

  return 0;
}

 

객체를 활용한 비교 함수 정의

#include <iostream>
#include <queue>

using namespace std;

class cmp{
  public:
    bool operator()(int a, int b){
      // 내림차순 정렬
      return a < b;
    }
};

int main(){
  priority_queue<int, vector<int>, cmp> pq;
  
  pq.push(3);
  pq.push(1);
  pq.push(4);

  // output: 4 3 1
  while(!pq.empty()){
    cout << pq.top() << " ";
    pq.pop();
  }

  return 0;
}

참고

https://cplusplus.com/reference/queue/priority_queue/

https://huilife.tistory.com/entry/C-Priority-Queue%EC%9D%98-custom-sort

https://www.geeksforgeeks.org/custom-comparator-in-priority_queue-in-cpp-stl/