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

우리가 흔히 아는 큐는 데이터가 rear에서 삽입되고 front에서 나가는(삭제) 선입선출(first-in first out) 구조의 자료구조입니다.

 

 

그렇다면 우선순위 큐(Priority Queue)는 무엇일까요?

 

우선순위 큐는 큐와 비슷하지만 다릅니다.

 

우선순위 큐의 모든 원소는 우선 순위가 있어 원소가 큐에서 제거되는 순서는 우선순위에 따라 결정됩니다. 보통 우선순위가 높은 원소가 가장 먼저 제거 대상이 됩니다.

 

그러므로 우선 순위 큐 내부의 모든 원소들은 오름차순, 혹은 내림차순으로 정렬된 채로 저장됩니다.

 

 

우선순위 큐를 구현하기 위해 다음과 같은 자료 구조를 이용할 수 있습니다.

1. 배열
2. 연결 리스트 (Linked List)
3. 힙 ( Heap data structure )
4. 이진 탐색 트리 ( Binary search Tree )