Priority Queue

자료구조	처리순서
Stack	LIFO : 나중에 들어온 데이터가 먼저 처리
Queue	FIFO : 먼저 들어온 데이터가 먼저 처리
Priority Queue	우선순위가 높은 데이터가 먼저 처리

우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저나온다.

• 시뮬레이션 시스템 (ex) 출발시간, 대기시간, 소요시간

• 네트워크 트래픽 제어

• 운영 체제에서의 작업 스케쥴링

데이터를 근거로 우선순위를 판단해야하며, 목적에 맞게 우선순위를 정해야한다. 우선순위가 같은 데이터도 존재할 수 있다.

우선순위 큐에서 가장 중요한 연산은 삽입(insert)과 삭제(delete)이다.

연산	설명
create()	우선순위 큐를 생성
init(q)	우선순위 큐 q 초기화
is_empty(q)	우선순위 큐 q가 비어있는지 검사
is_full(q)	우선순위 큐 q가 가득찼는지 검사
insert(q,x)	우선순위 큐 q에 x추가
delete(q)	우선 순위큐로부터 가장 우선순위가 높은 요소 삭제, 반환
find(q)	우선순위가 가장 높은 요소 반환

구현방법

우선순위 큐는 3가지 방법으로 구현할 수 있다.

1. 배열을 기반으로 구현

2. 연결리스트를 기반으로 구현

3. 힙(Heap)을 이용하는 방법

배열과 연결리스트

배열이나 연결리스트를 이용해서 구현하면 힙보다는 간단하게 구현할 수 있으나 단점이 있다.

배열

• 데이터 삽입 및 삭제에서 데이터를 이동하는 연산을 계속해야한다. (당기거나 밀어야하는)

• 삽입 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위를 비교해야한다.

연결리스트

• 삽입 위치를 찾기위해서 모든 노드에 저장된 데이터와 우선순위를 비교해야한다.

데이터가 적은 경우에는 단점이 아닐 수도 있지만 데이터가 많아지면 비교할 대상이 많아져 성능이 저하된다.

힙(Heap)

• 힙은 완전이진트리로 구현한다. 힙에 대한 자세한 설명은 힙(Heap) 게시물에서 했다.

표현방법	삽입	삭제
순서없는 배열	O(1)	O(n)
순서없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결리스트	O(n)	O(1)
힙(Heap)	O(logn)	O(logn)

이러한 성능차이로 주로 Heap을 이용해서 우선순위큐를 구현하는 것이 일반적이다.