[C++ STL] priority_queue

▤ 목차

Priority_queue 란?

C++ 표준 라이브러리의 컨테이너 중 하나로, 우선순위 큐를 구현한다.

우선순위 큐는 가장 큰(또는 가장 작은) 요소가 항상 먼저 나오는 특수한 형태의 큐이다.

 

1. priority_queue의 기본 구조

내부적으로 priority_queue는 힙 자료구조를 사용한다. 주로 배열 또는 vector를 기반으로 구현한다.

• 기본형태

priority_queue<T, Container, Compare>

• 세 가지 주요 요소로 구성된다.

1. Type : 저장할 요소의 자료형.
2. Container : 내부적으로 요소를 저장할 컨테이너, 기본값은 vector<Type> 인다.
3. Compare : 요소를 비교하는 함수 객체, 기본값은 less<Type> 이다.

 

2. 주요 멤버 함수

1. empty : 큐가 비어 있으면 true , 그렇지 않으면 false를 반환한다.
2. size : 큐의 요소 개수를 반환
3. top : 큐의 맨 앞에 있는 요소를 반환한다. ( 최대 힙의 경우 가장 큰 요소)
4. push : 요소를 큐에 추가하고 힙 특성을 유지한다.
5. emplace : 요소를 직접 생성하여 큐에 추가한다.
6. pop : 큐의 맨 앞에 있는 요소를 제거하고 힙 특성을 유지한다.
7. swap : 다른 우선순위 큐와 요소를 교환한다.

 

🤔push와 emplace는 요소를 삽입하는 동일한 기능을 하는데 차이가 뭘까?

push 함수와 emplace 함수는 요소를 삽입하는 동일한 기능을 하지만, 객체를 생성하는 시점이 다르다. push는 객체를 생성한 후, 이를 컨테이너에 복사하거나 이동하지만, emplace는 컨테이너 내부에서 객체를 생성하기 때문에 불필요한 복사나 이동이 없어 더 효율적이다.

즉, push는 객체를 미리 생성한 후 삽입하는 반면, emplace는 삽입하면서 객체를 생성한다.

 

3. 기본 사용법

priority_queue의 기본 선언과 사용

• 기본적으로 최대 힙으로 동작한다. 즉, 가장 큰 요소가 먼저 나온다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
  priority_queue<int> pq;

  pq.push(10);
  pq.push(30);
  pq.push(20);
  pq.push(5);

  while (!pq.empty()) {
    cout << pq.top() << " ";
    pq.pop();
  }

  return 0;
}

// 출력 : 30 20 10 5

 

최소 힙으로 사용하기

• 최소 힙으로 동작하게 하려면 greater <T>를 사용해야 한다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
  priority_queue<int, vector<int>,  greater<int>> pq;

  pq.push(10);
  pq.push(30);
  pq.push(20);
  pq.push(5);

  while (!pq.empty()) {
    cout << pq.top() << " ";
    pq.pop();
  }

  return 0;
}

// 출력 : 5 10 20 30