우선순위 큐 (Priority Queue)

우선순위 큐는 원소를 push하는 방법은 기존의 큐와 똑같지만 삭제 연산을 할 때

 우선순위가 높은 원소 순서대로 제거 하는 큐이다.

그림처럼 원소를 1 -> 3 -> 4 -> 5 순서로 push한다.

큐 안에 push 된 원소들은 1, 3, 4, 5 순서대로 있지만 우선순위 큐에서는 우선순위를 부여하여 

우선순위가 가장 높은 순서대로 원소를 제거 한다.

그림상에서는 숫자가 큰 순서대로 우선순위가 크다고 가정했다.

우선순위 큐는 배열로 구현 할 수 있는데, 삽입 연산은 그대로 큐의 끝에 원소를 삽입하여 O(1)의 시간이 걸린다.

하지만 삭제 연산을 할 때, 배열의 처음부터 큐의 길이 까지 우선순위를 탐색하여 가장 큰 원소를 삭제하고

그 다음에 삭제한 원소의 빈자리를 오른쪽에서 부터 한칸씩 당겨야 하기 때문에 O(n)의 시간이 걸린다.

삭제를 할 때에 입력이 커지게 되면 시간이 오래 걸려서 비효율적이다.

삭제연산을 줄이기 위해서 힙을 이용하여 우선순위 큐를 구현할 수 있는데, 

그러면 O(log n) 의 시간만에 삭제 연산을 할 수 있다. O(n)과 O(log n)의 차이는 엄청나기 때문에 

힙을 이용한 우선순위 큐의 구현은 배열을 이용한 구현보다 비교도 안 될 만큼 빠르다고 할 수 있다. 

이 부분에 대해서는 힙에서 자세히 정리 할 것이다.

출처 : AlgorithmLABS