[Data Structure] Priority Queue(우선순위 큐)

 

우선순위 큐

큐의 변형된 자료구조로 각 요소에 우선순위가 부여되고 우선순위에 따라서 요소를 삽입하거나 삭제한다

일반적인 큐의 선입선출(FIFO) 규칙을 따르지 않고 우선순위가 높은 요소가 먼저 처리된다.

 

• 최소 우선순위 큐 : 가장 낮은 우선순위의 요소가 먼저 처리
• 최대 우선순위 큐 : 가장 높은 우선순위의 요소가 먼저 처리

연산

• 삽입 : 새로운 요소를 우선순위를 고려하여 큐에 추가
• 삭제 : 우선순위가 가장 높은 요소를 큐에서 제거

삽입 또는 삭제 후에도 항상 우선순위에 따라 정렬된 상태를 유지한다

 

일반 큐와 차이점

• 선입선출 규칙을 따르지 않고 우선순위를 고려함
• 일반 큐는 정렬되지 않지만 우선순위 큐는 정렬된 상태를 유지함

구현 방법

 

배열 또는 리스트를 사용한 구현

• 삽입 시 순차적으로 추가
• 삭제 시 우선순위를 검색하여 제거
• 삽입, 삭제 시 전체 배열을 탐색해야 하므로 비효율적 O(n)

정렬된 배열 또는 리스트를 사용한 구현

• 삽입 시 우선순위에 따라 정렬된 위치에 삽입
• 삭제 시 첫번째 또는 마지막 요소를 제거
• 삽입 시 정렬 작업이 필요하여 O(n)의 시간복잡도를 가짐

힙을 사용한 구현

• 힙 속성 덕분에 항상 정렬된 상태를 유지
• 삽입 삭제 모두 O(log n)의 시간복잡도
• 우선순위 큐를 효율적으로 구현하는 가장 일반적인 방법
• 배열 또는 리스트보다 구현 난이도가 비교적 복잡

 

활용사례

• 운영체제 프로세스 스케줄링
• 네트워크 패킷 스케줄링

 

우선순위 큐 구현

 

배열

https://github.com/9mans/tree-practice/blob/master/src/priorityQueue/ArrayPQ.java

정렬된배열

https://github.com/9mans/tree-practice/blob/master/src/priorityQueue/SortArrayPQ.java

힙

https://github.com/9mans/tree-practice/blob/master/src/priorityQueue/HeapPQ.java