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

Priority Queue

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

일반적인 큐 : FIFO(선입선출)

특징

• 모든 항목에 우선순위가 있다.
• 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 나간다.
• 두 요소의 우선순의가 같으면 queue의 순서에 따라 처리됨

기본 동작

enqueue()	queue에 새 요소 삽입
dequeue()	queue에서 최대 우선 순위 요소 삭제 후 그 값 반환
peek()	queue에서 최대 우선 순위 요소를 반환

 

enqueue()

1. 힙 끝에 새 요소 삽입
2. 부모 노드와 비교하여 우선순위에 맞게 위치 변경 (여기서 우선순위는 숫자가 클수록 우선순위도 높다)
3. 힙 속성이 유지될 때까지 2번 반복

 

dequeue()

1. 루트 노드 값 추출
2. 힙의 마지막 요소를 루트에 배치
3. 마지막 요소 삭제
4. 루트 노드부터 자식노드와 비교하여 우선순위 알맞게  위치 변경