1. 개념
- 우선순위큐
- Queue의 한 종류이며 그냥 선입선출의 개념이 아니라 지정된 우선순위에 따라 값들이 정렬되어 있는 Queue
일반적인 Queue라면 먼저 넣은 값이 앞에, 더 나중에 넣은 값이 뒤에 순서대로 들어가지만
Priority Queue는 값이 들어가면 지정된 우선순위대로 Queue가 정렬되고, pop은 정렬된 Queue의 앞에서 이루어짐
Heap으로 구현되어 있으므로 Push 후 정렬되는 과정은 O(logN)으로 이루어짐 - 큐에 먼저 들어간 값이 앞에 가는게 아니라 지정된 우선순위에 따라 값이 앞으로 가는 방식
- 가장 우선순위가 높은 값이 front를 유지한다.
- 기본값으로는 가장 큰 값이 가장 앞으로 감
- 다만 항상 완벽한 정렬상태를 유지하는 것이 아닌 첫번째 원소만 루트 node에 있고 나머지는 느슨한 정렬상태
2. 구현
- C++기반의 Priority_queue STL : https://smallpants.tistory.com/211
3. 시간복잡도
- insert : O(logN)
- pop : O(1) // 1번노드를 가져오면 되므로
- 탐색 : O(N)
- erase : O(N) // 먼저 탐색 후 삭제해야 하므로