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

일반적인 큐 자료구조는 뒤에서 자료를 추가하고, 앞에서 자료를 삭제한다.

 

우선순위 큐도, 이름이 큐인 만큼 기본적으로 이런 구조를 가진다. 단, 앞에 우선순위라는 말이 이 자료구조의 정체성을 나타낸다.

 

들어오는 자료구조에서 우선순위를 판별하여 우선순위가 높은 자료를 앞쪽에 배치한다. 따라서 우선순위 큐에서 항상 먼저 나오는 데이터는 우선순위가 가장 높은 자료이다.

 

 

구조

 

1. 데이터가 큐에 삽입이 되면 기본적으로 push_back되고, 삭제를 하면 pop_front가 된다. 이는 일반적인 큐와 동일하다.

 

우선순위 큐 기본 구조

 

2. 삽입되는 과정에서 각 자료들과 우선순위를 비교한다. 만약 먼저 삽입된 데이터들보다 우선순위가 높다면 그 데이터는 다른 데이터보다 앞쪽으로 배치가 된다.

 

3. 삽입을 enqueue, 삭제를 dequeue라고 표현한다. 이 연산은 각각 배열, 연결 리스트, 정렬된 배열, 정렬된 리스트, 힙 구조에 따라 다른 시간복잡도를 가진다.

 

	삽입(enqueue)	삭제(dequeue)
배열	O(1)	O(N)
연결 리스트	O(1)	O(N)
정렬된 배열	O(N)	O(1)
정렬된 연결 리스트	O(N)	O(1)
힙	O(logN)	O(logN)

 

위에서 확인이 가능한 것처럼, 각각 삽입과 삭제에서 배열과 연결 리스트는 정렬되지 않은 상태와 정렬된 상태에서 한 쪽은 효율이 좋지만, 다른 한 쪽은 매우 효율이 나쁘다. 때문에 우선순위 큐는 주로 힙 구조를 이용해서 만들어진다.