[C++][자료구조] 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)는 요소들을 우선순위에 따라 저장하고 접근하는 자료구조이다.
우선순위 큐(Priority Queue)는 <queue> 헤더에 있는 std::priority_queue 클래스를 사용 할 수 있다.

---

1. 우선순위 큐(Priority Queue) 기본적인 사용

여느 때와 같이 queue 사용법과 거의 비슷하다.

삽입 한 요소는 container 내부적으로 우선순위에 따라 정렬 됨.

#include <queue>
std::priority_queue<int> pq

pq.push(10);			// push() 함수 : 우선순위 큐에 요소를 추가
pq.push(5);
pq.push(20);

최상위 요소 접근, 제거

int highestPQ = pq.top(); 	//현재 우선순위 큐에서 가장 높은 우선순위를 가진 요소에 접근.
pq.pop();					//현재 우선순위 큐에서 가장 높은 우선순위를 가진 요소를 제거.

---

2. 우선순위 큐(Priority Queue)의 시간 복잡도.

요소를 추가, 제거할 때 내부적으로 이진 힙(Binary Heap)구조로 최적화되어, 가장 높은 우선순위 요소에 빠르게 접근할 수 있다.

1. 삽입 (Insertion) : O(log n) : 이진 힙(Binary Heap)을 사용하는 경우, 데이터 삽입시 (log n) 이 걸림.

2. 최상위 요소 접근 (Access Minimum/Maximum) : O(1)

3. 최상위 요소 제거 (Deletion of Minimum/Maximum) : O(log n)

4. 요소 개수 확인: O(1)
   
   

---

3. 우선순위 큐(Priority Queue)의 알고리즘 활용.

1. 다익스트라 알고리즘 (Dijkstra's Algorithm):

   • 가장 짧은 경로를 찾는 알고리즘.
   • 각 노드까지의 최단 거리를 유지하면서 노드를 탐색하며 최단 경로를 찾을때.

2. 프림 알고리즘 (Prim's Algorithm):

   • 최소 신장 트리(Minimum Spanning Tree)를 찾는 알고리즘.
   • 정점들을 연결하면서 최소 비용을 유지하며 트리를 확장하는데 활용.

3. A* 알고리즘 (A-star Algorithm):

   • 지정된 출발점에서 목표 지점까지 최단 경로를 찾는 알고리즘.
   • 휴리스틱 함수와 함께 사용하여 최적 경로를 탐색.

4. 힙 정렬 (Heap Sort):

   • 정렬 알고리즘 중 하나로, 우선순위 큐를 활용하여 정렬.

5. 크루스칼 알고리즘 (Kruskal's Algorithm):

   • 그래프에서 가장 적은 비용으로 모든 노드를 연결.
   • 간선들을 가중치에 따라 정렬하고, 우선순위 큐를 사용하여 사이클을 방지하면서 최소 신장 트리 구성.

6. 위상 정렬 (Topological Sort):

   • 방향 그래프에서 노드 간의 위상을 정렬.
   • 선행 조건을 갖는 작업들을 순서대로 정렬.

7. 문자열 검색 알고리즘( ex)Efficient String Searching ):

   • 우선순위 큐로 인덱스를 관리하면서, 먼저 발견된 패턴을 큐에서 꺼냄.