우선순위 큐

• 우선순위가 높은 순서대로 반환하는 자료구조

1. 구현

• 내부 구조는 heap으로 구현되어 있다.
• C++에서는 라이브러리로 제공된다.

2. 선언 방법

priority_queue<'자료형', '구현체', '비교연산자'> 이름;

• 자료형 : int, double, pair 등 기본 자료형 및 구조체, 클래스 등을 사용한다.
• 구현체 : 보통 vector<자료형>으로 구현한다. 지정하지 않으면 vector로 기본 적용.
• 비교연산자 : 비교를 위한 기준을 알려준다.

2-1. 비교 연산자 사용 예시 (정렬 예시)

1. 내림차순 - 최대힙

   priority_queue<int> pq;

   • 기본적으로 내림차순 정렬이다.

2. 오름차순 - 최소힙

   priority_queue<int, vector<int>, greater<int>> pq;

   • 비교연산자에 greater<int>를 사용하면 오름차순으로 정렬된다.

3. 사용자 설정

   struct compare
   {
   	bool operator()(int a, int b)
       {
       	return a > b;	// priority_queue에 적용 시 부모 노드와 크기를 비교해
           				// a가 b보다 크면 true를 리턴해 swap할 것
       }
   }
   
   int main()
   {
   	priority_queue<int, vector<int>, compare> pq;
   }

   • 직접 비교연산자를 만들어 사용할 수 있다.

3. 주요 메소드

• push() : 우선순위 큐에 원소를 추가한다
• pop()  : 우선순위 큐에서 top의 원소를 제거한다
• top() : 우선순위 큐에서 top에 있는 원소, 즉 우선순위가 높은 원소를 반환한다.
• empty() : 우선순위 큐가 비어있으면 true를 반환하고 그렇지 않으면 false를 반환한다
• size() : 우선순위 큐에 포함되어 있는 원소의 수를 반환한다

4. 사용 예시

4-1. 내림차순, 오름차순 예시

• 내림차순 - 최대힙

  • 출력 결과: 8, 5, 2, 1

    priority_queue<int, vector<int>, less<int>> pq1;
    
    pq1.push(5);
    pq1.push(2);
    pq1.push(8);
    pq1.push(9);
    pq1.push(1);
    pq1.push(14);
    
    pq1.pop();
    pq1.pop();

• 오름차순 - 최소힙

  • 출력 결과: 5, 8, 9, 14

    priority_queue<int, vector<int>, greater<int>> pq2;
    
    pq2.push(5);
    pq2.push(2);
    pq2.push(8);
    pq2.push(9);
    pq2.push(1);
    pq2.push(14);
    
    pq2.pop();
    pq2.pop();

4-2. pair 구조체를 사용할 시

• pair 구조체 사용 예시
  • 구조체 삽입 시 구조체의 first의 값을 기준으로 정렬된다.
  • 구조체 삽입 시 emplace를 유용하게 사용할 수 있다.

    priority_queue<pair<char, int>> pq;
    
    pq.push(pair<char, int>('a', 2)); // push 사용 시 pair<char, int>()로 오브젝트 생성
    pq.emplace('b', 1);		// emplace 사용 시 pair 오브젝트 만들지 않고 바로 값을 입력

    • 출력 결과: b 1 \ a 2