PriorityQueue 는 이름에는 queue가 들어가지만, queue와 다르게 pop을 할 때 지정한 규칙(기본적으로는 큰 값)에 따라 값을 추출할 수 있습니다.
queue의 경우 FIFO구조를 통해 먼저 들어간 값을 먼저 꺼내지만, PriorityQueue의 경우 내부구조가 Heap으로 이루어져있어 이진트리의 성질을 보입니다.
priority_queue는 위와 같은 template 인자를 받습니다.
typename: pq에서 사용할 원소의 타입을 설정합니다.
_Pr: predicate를 설정합니다.
보는 것처럼 기본 설정은 container=vector, _Pr는 less입니다. (less라면 큰 값 부터 pop)
priority_queue의 내부 생성자를 확인해보면 _Make_heap()을 호출해 heap을 만드는 것도 확인할 수 있습니다.
Heap의 경우는 시간 복잡도가 아래와 같습니다.
| top() / 최댓값 확인 | O(1) | root에 최댓값/최솟값이 있음 |
| push() / 삽입 | O(log N) | 맨 뒤에 넣고 부모 방향으로 올라감 |
| pop() / 최댓값 제거 | O(log N) | root 제거 후 아래로 내려가며 정렬 |
| make_heap() / 힙 생성 | O(N) | 전체 배열을 한 번에 heapify |
| 임의 원소 탐색 | O(N) | heap은 전체 정렬 구조가 아님 |
| 임의 원소 삭제 | 보통 O(N) | 해당 원소를 먼저 찾아야 함 |
priority queue의 사용자체는 predicate의 사용법을 알면 간단합니다.
함수 혹은 lambda 사용법만 알면 더 유용하게 활용할 수 있겠네요