[C++/STL] - priority_queue

1. priority_queue란

priority_queue는 C++의 STL에서 제공하는 컨테이너 어댑터 중 하나로, 우선순위 큐를 구현하는 데 사용됩니다. priority_queue를 사용하면 최댓값 또는 최솟값을 상수 시간 내에 찾을 수 있습니다.

2. 특징

• priority_queue는 우선순위 큐를 구현하는 데 사용되는 컨테이너 어댑터입니다.
• priority_queue는 내부적으로 힙(Heap) 자료구조를 사용하여 구현됩니다. 이를 통해 삽입과 삭제를 O(log n)의 시간 복잡도로 처리할 수 있습니다.
• priority_queue의 기본 동작은 가장 큰 값이 우선순위가 높은 것으로 간주합니다. 이를 바꾸려면 비교 함수를 지정해야 합니다.
• priority_queue는 입력된 값을 내부적으로 정렬합니다.
• priority_queue는 동일한 값을 여러 번 삽입할 수 있습니다.
• priority_queue는 내부적으로 복사 생성자와 대입 연산자를 사용합니다. 따라서 사용자 정의 자료형을 사용할 경우, 이러한 함수를 정의해주어야 합니다.

3. 장단점

장점 :

• priority_queue는 우선순위 큐를 구현하는 데 사용하기 적합합니다. 우선순위 큐는 일반적인 큐와 달리 가장 높은 우선순위를 가진 원소가 항상 맨 앞에 위치하므로, 빠르게 최대값 또는 최소값을 찾을 수 있습니다.
• priority_queue는 내부적으로 힙(Heap) 자료구조를 사용하여 구현됩니다. 이로 인해 삽입과 삭제를 O(log n)의 시간 복잡도로 처리할 수 있습니다.
• priority_queue는 다양한 자료형을 다룰 수 있습니다. 또한 사용자 정의 자료형도 사용할 수 있습니다.

단점 :

• priority_queue는 내부적으로 정렬을 수행합니다. 이로 인해 삽입과 삭제 시간이 느릴 수 있습니다.
• priority_queue는 동일한 값을 여러 번 삽입할 수 있습니다. 따라서 중복된 값을 처리해야 하는 경우에는 추가적인 작업이 필요합니다.
• priority_queue는 내부적으로 복사 생성자와 대입 연산자를 사용합니다. 따라서 사용자 정의 자료형을 사용할 경우, 이러한 함수를 정의해주어야 합니다.

4. 시간복잡도

1. 접근 - O(1)
   원소 접근 : priority_queue는 내부적으로 힙(Heap) 자료구조를 사용하여 구현됩니다. 따라서 가장 우선순위가 높은 원소에 대한 접근은 O(1)의 시간 복잡도로 가능합니다. 그러나 우선순위가 낮은 원소에 대한 접근은 불가능합니다.
2. 검색 - O(n)
   검색 : priority_queue는 내부적으로 정렬되어 있습니다. 따라서 특정 값을 검색하는 데는 O(n)의 시간 복잡도가 필요합니다.
3. 삽입 및 삭제 - O(log n)
   삽입 및 삭제 : priority_queue는 내부적으로 힙(Heap) 자료구조를 사용하여 구현됩니다. 이를 통해 삽입 및 삭제를 O(log n)의 시간 복잡도로 처리할 수 있습니다.

따라서 priority_queue는 우선순위 큐에서 가장 높은 우선순위를 가진 원소에 대한 삽입과 삭제를 빠르게 처리할 수 있지만, 낮은 우선순위의 원소에 대한 검색은 느릴 수 있습니다.

5. 사용법

1) 초기화

//기본 생성자: priority_queue 객체를 생성할 때, 아무런 인자를 전달하지 않는 기본 생성자를 사용하여 초기화할 수 있습니다. 이 경우, priority_queue는 비어있는 상태가 됩니다.
//원소를 포함하는 벡터로부터 초기화: priority_queue 객체를 생성할 때, 원소를 포함하는 벡터를 전달하여 초기화할 수 있습니다. 이 경우, 벡터의 원소들은 우선순위 큐에 삽입됩니다. 예를 들어, 다음과 같이 초기화할 수 있습니다.
vector<int> vec = {3, 1, 4, 1, 5, 9};
priority_queue<int> pq(vec.begin(), vec.end());

int arr[] = {3, 1, 4, 1, 5, 9};
priority_queue<int> pq(begin(arr), end(arr));

// cmp라는 이름의 우선순위 비교 함수를 따라 정렬하는 우선순위 큐
priority_queue<int, vector<int>, cmp> pq;

2) 멤버 함수

push(): 우선순위 큐에 원소를 추가합니다.
pop(): 우선순위 큐에서 가장 우선순위가 높은 원소를 제거합니다.
top(): 우선순위 큐에서 가장 우선순위가 높은 원소에 접근합니다.
empty(): 우선순위 큐가 비어있는지 여부를 반환합니다.
size(): 우선순위 큐에 저장된 원소의 개수를 반환합니다.