Priority Queue

목차
1. 우선순위 큐

들어가기 전에..

• 1. Queue는 FIFO 구조의 선형 자료구조

---

1. 우선순위 큐

• 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 것
• 속성
  1. 모든 항목에는 우선순위 존재하며, 높은 녀석이 먼저 나감
  2. 우선순위가 같으면 queue 순서에 따라서

• 사용방법

peek() : 최대 우선 순위 요소 반환(값 제거 X), O(1)
1. 루트(최상단 노드) 값 반환
int peek(int aa[]) { return arr[1]; }

enuqeue() : 새 요소 삽입
1. Heap 끝에 새 요소 삽입
2. 부모 노드와 비교, 우선순위가 높다면 노드 값 바꾸기
3. Heap 속성이 유지될 때까지(우선순위) 2 반복

dequeue() : 최대 우선 순위 요소 삭제, 값 반환
1. 루트 노드값 추출
2. heap 마지막 요소를 루트 노드에 위치
3. 마지막 요소 제거 및 Heapify() 수행

*Heapify(): Heap속성 유지(위에서 아래로 내려가며-> 양쪽 자식노드와 우선순위 비교)

• 구현방식에 따른 시간복잡도
  
  
  

---

우선순위 큐의 사용사례

• CPU 스케쥴링
• 다익스트라, 프림 알고리즘
• 우선순위를 포함한 모든 queue 응용

*출처 : https://yoongrammer.tistory.com/81