Priority Queue 소개

Priority Queue는 각각 배열들의 우선순위에 의해 정렬된 큐를 말한다.

사실 Queue도 자료구조시간에 배웠는데, 일반적인 큐가 선입선출 구조를 갖는 반면에
Priority Queue는 먼저 입력했다고 해서 먼저 수행되지는 않다는 차이가 있다.

 

이런 우선순위 큐는 주로 CPU Scheduling 이나
Huffman coding algorithm을 사용하는 Data Compression, 짧은 길찾기 문제에서 Dijkstra’s algorithm을 사용할 때, Minimum spanning tree 에서 Prim’s algorithm 등등 사용된다.

 

그럼 Priority Queue는 어떻게 구현할 수 있을까?

이것을 구현하기 위해선 배열과 linked list, 그리고 저번에 배웠던 Heap이 필요하다.

https://guhonga.tistory.com/87

Heap sort 소개

 

이걸 이용해서 우선순위 큐를 구현하는데, 구현의 핵심이 되는 연산은 Get Maximum, Extract Maximum (deletion),  Increase Key, Insertion 이 있다. 차례대로 알아보자.

 

 

Get Maximum 연산은 O(1)의 시간복잡도를 갖는다. 그냥 가장 높은 우선순위의 element를 검색하는 기능이다.
(처음에 우선순위가 이미 정렬된 거 생각 못하고 전체 한번 scan해야 하지 않나? 해서 O(n)인줄.. ㅋㅋ..)

 

 

Extract Maximum (deletion) 은 O(log n)이다.
우선 가장 높은 우선순위의 element를 추출하고, Max-Heapify를 사용하여 priority queue를 재구성한다.

이건 Extract Maximum (deletion)의 슈도코드

Heap-Extract-Max(A)
if A.heap-size<1
	error "heap underflow"
max = A[1]
A[1] = A[A.heap-size]
A.heap-size = A.heap-size -1
Max-Heapify(A, 1)
return max

 

 

Increase Key 연산은 O(log n).
x번째의 키값을 새로운 값 k로 증가시키는 연산이다. 

x부터 root node까지 새로 증가된 키 값에 적절한 장소를 찾기 위해 트리를 순회한다.
위의 예시 그림에서는 4의 값을 15로 증가시키고 적절한 자리로 이동하는 모습이다.

Heap-Increase-Key(A,i,key)
if key<A[i]
	error "new key is smaller than current key"
A[i] = key
while i>1 && A[Parent(i)] < A[i]
	swap A[i],A[Parent(i)]
	i = Parent(i)

 

 

마지막으로 Insertion 연산은 O(log n)의 시간복잡도를 갖는다.
새로운 leaf node를 추가함으로서 max-heap을 확장하는 연산이다.

이 연산에는 새로운 leaf node의 key를 설정하는 기능과, max-heap property를 유지하는 기능이 있다.

Max-heap-insert(A,key)
A.heap-size = A.heap-size + 1
A[A.heap-size] = -infinite
Heap-Increase-Key(A, A.heap-size, key)