(작성중) [자료구조] 우선순위 큐란? (Priority Queue)

등장배경

- 일반적인 큐에 대해서는, 데이터마다 우선순위(레벨)이 정해져있지 않았다.  즉, 우선순위가 정해져있지 않았다.

- 그래서, 문제가 생긴다. 큐를 사용한 처리방식에서, 데이터마다 빨리 처리해야할 우선순위가 있다면, 어떻게 대처할 것인가?

- 아래의 기존전략 [1. 일반적인 큐 사용], [새로운전략 2. 우선순위 큐]의 비교를 통해 이해해보자.

 

기존전략 1. 일반적인 큐 사용

- 만약, 아이스크림 가게에서, 아래와 같이 줄 서 있는 사람들을 생각해보자.

각각의 박스는 사람을 의미하며, 박스 안에 있는 숫자는 대기시간을 의미한다. (사람마다 주문하는 메뉴가 다르기 때문에, 대기시간 또한 사람마다 다를 수 있다.)

 

총 대기시간의 평균은 어떻게 되겠는가?

(20+30+32+37) = 119/4 =~ 30, 대략 평균 30초가 걸린다.

 

각각의 사각박스는 고객이 기다리는 시간을 의미한다.

 

 위는 문제가 있다. (일반적인 큐로 사람을 줄세울 때에는)

무엇이 문제냐면, 맨 뒤에있는 사람은 5초안에 처리될 문제를, 앞에있는 사람때문에 대기시간이 늘어난다는 점이다.

즉, 들어오는 순서는 고려했지만, 대기시간(key값)은 고려되지 않았다. 그래서 문제이다.

 

하지만, 아래처럼 대기시간을 고려하여 줄세우면 어떨까?

 

새로운전략 2. 우선순위 큐 사용

 

아래처럼 줄 세웠을 때 평균 대기시간은?  

(2+7+17+37)/4 = 63/4 =~ 16. 대략 평균 16초가 걸린다.

 

 

즉, 가장 앞에 있는 사람은, 대기시간이 짧은 사람으로 배치하는 전략이다.

이렇게 되면, 평균 대기시간이 많이 줄어든 것을 알 수 있다.

 

 당신이 아이스크림 사장이라면 매출을 높이기 위해, 어떤 전략으로 줄세우기를 할 것인가?

 

고려해야될 점은, 우선순위 큐 사용은, 새로운 사람이 들어올 때 마다, 이 순서를 재배열해야된다는 점이다.

만약, 위의 큐에서 2초보다 짧은 대기시간을 가진 손님이 들어오면, 그 손님을 제일 앞에 세워야 할 것이다.

그래서, 손님끼리 자리를 바꾸는 연산이 필요할 것이다.

 

 

 

위의 이유때문에, 우선순위 큐가 등장하였다.

 

큐와 우선순위 큐 비교

	큐 (Queue)	우선순위 큐 (Pirority Queue)
순서	넣은 시간에 따라 (먼저 넣은 것이 먼저 나감, FIFO)	Key 값에 따라 (낮은 순서, 혹은 높은 순서)
데이터마다 레벨이 있느냐	없다.	있다. Key값이 데이터의 레벨이 된다.
새로운 데이터가 들어온다면,	맨 뒤에 추가	적절한 위치를 알아내기 위해, 추가적 연산 필요.

 

의미/특징

- 큐의 종류 중에 하나이다.  (그리고, Abstract data type 중 하나)

- 우선순위 큐의 구현은, Binary Heap(바이너리 힙, 이진 힙)을 이용하여 구현한다.

(Binary Heap에 대한 설명 및 코드는 아래의 게시글에 있다.)

https://i5i5.tistory.com/559

[자료구조] 이진 힙, 바이너리 힙 (Binary Heap) 이란?

 

코드

이미 구현한 Binary Heap을 이용하여, 우선순위 큐를 구현한다.

(Binary Heap 구현은, 이 게시글을 참고하면 됩니다. https://i5i5.tistory.com/559 )

 

Java

 

 

인용/참고자료

한양대학교 - 데이터 구조론 (우선순위 큐)

http://www.kocw.net/home/cview.do?cid=ec066a0f24e13e9a 

 

 

 

도움이 되셨으면 "공감"버튼을 눌러주실 수 있을까요?

더 많은 도움을 드리는 게시글을 작성하겠습니다.