10 우선순위 큐

10.1 우선순위 큐

도로에서 사이렌을 울리는 구급차나 소방차가 일반 승용차보다 우선순위가 높은 것처럼, 컴퓨터에서도 우선순위의 개념이 필요할 때가 있다. 예를 들어 네트워크 패킷 중에서 네트워크 관리와 관련된 패킷은 다른 것들보다 우선순위를 가진다. 따라서 자료구조에서도 이러한 우선순위를 지원할 필요가 있다. 

 

우선순위 큐Priority Queue는 이런 우선순위의 개념을 도입한 자료구조로, 마치 FIFO 원칙을 따르는 큐처럼, 우선순위를 가진 데이터들 중  높은 순 먼저 출력한다. 다양한 방법으로 구현이 가능하지만 가자 효율적인 구조는 힙heap이다. 따라서 우선순위 큐를 힙 트리Heap Tree라고도 부른다.

 

우선순위 큐 추상 자료형

우선순위 큐는 우선순위 값을 가진 요소들의 모임이다. 역시 요소의 삽입, 삭제 연산이 중요한데 우선순위 큐는 삭제 연산에서 어떤 요소가 먼저 삭제되는 가에 따라 최소 우선순위 큐와 최대 우선순위 큐로 나뉜다. 최대 우선순위 큐는 우선순위가 높은 순으로, 최소 우선순위 큐는 우선순위가 낮은 순으로 먼저 삭제한다. 

 

객체: 우선순위를 가진 요소들의 모음

연산:

insert(item): 우선순위 큐에 항목 item을 추가한다

remove(): 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 반환한다

find(): 우선순위가 가장 높은 요소를 반환한다 (삭제 x)

isEmpty(): 우선순위 큐가 공백 상태인지 검사한다

isFull(): 우선순위 큐가 포화 상태인지 검사한다

display(): 우선순위 큐의 모든 요소들을 출력한다