자료구조 - 우선순위 큐 (Priority Queue)

우선순위 큐

들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옴

우선순위 큐의 구현 방식 중, 힙이 O(log n)을 보장하므로 일반적으로 힙을 통해 구현

• 모든 항목에는 우선순위가 존재
• 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 Queue에서 출력
• 두 요소의 우선 순위가 같으면 Queue의 순서에 따라 제공

[ 활용 예시 ]
- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- 운영 체제의 작업 스케쥴링

---

Peek

최대 우선순위 값을 반환
최대 우선순위 값(최대 힙)은 항상 루트에 존재

Enqueue

우선순위 큐에 요소를 삽입하는 작업

1. 힙 끝에 새 요소를 삽입
2. 부모 요소와 비교, 힙 속성을 위배하는 경우 부모 노드와 자리 교체
3. 힙 속성이 유지될 때까지 2번 작업 반복

Heapify

힙 속성을 유지하는 작업
위에서 아래로 진행

1. 자식 노드와 우선순위를 비교
2. 만약 자식 노드 우선순위가 높다면 왼쪽 오른쪽 자식 중 가장 우선순위가 높은 노드와 교환
3. 힙 속성이 유지 될 때까지 1,2번 과정을 반복

Dequeue

최대 우선순위 요소를 삭제하고 그 값을 반환

1. 루트 노드의 값을 추출
2. heap 마지막 요소를 루트 노드에 배치
3. 마지막 요소는 제거
4. 루트 노드부터 heapify를 수행

---

출처 : 사진 클릭 시 이동