비선형 자료구조 - 5. 우선순위 큐

우선순위 큐 (Priority Queue)

일반적인 큐의 방식(First In, First Out)과 다르게, 데이터에 우선순위를 부여하고 우선순위가 높은 데이터가 먼저 나오는 자료형을 우선순위 큐라고 합니다.

 

 

우선순위 큐 구현

우선 순위 큐는 배열, 연결 리스트, 힙을 통해 구현할 수 있습니다.

 

자료구조별 시간복잡도는 다음과 같습니다.

	enqueue 연산	dequeue 연산
정렬된 배열	O(N)	O(1)
정렬된 연결 리스트	O(N)	O(1)
힙	O(logN)	O(logN)

 

일반적으로 시간복잡도 때문에 우선순위 큐는 힙으로 구현하는 편입니다. 

 

 

프로그래밍 언어로 구현

Java

자바에선 기본적으로 제공하고 있습니다.

PriorityQueue pq = new PriorityQueue<>();