Data Structure - Priority Queue

우선순위 큐 (Priority Queue)

일반적인 Queue는 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 linear Data Structure.  하지만 Priority Queue는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 Queue.

일반 queue - 처음 줄 선 순서대로 / 특수 queue - 우리가 지정한 어떠한 순서대로

 

Priority Queue의 속성 :

ㆍ모든 항목에는 우선순위가 있음.

ㆍ우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 제외됨.

ㆍ두 요소의 우선 순위가 같으면 queue의 순서에 따라 제공됨.

 

Priority Queue가 지원하는 기능

ㆍenqueue() : queue에 새 요소 삽입

ㆍdequeue() : queue에서 최대 우선 순위 요소를 삭제하고 그 값을 return.

ㆍpeek() : queue에서 최대 우선 순위 요소 return.

 

일반적인 Priority Queue 구현 방식 (배열, 리스트, 힙) 

각 구현 방식에 대한 시간 복잡도 ->

구현방법                                                enqueue()                     dequeue()

배열(unsorted array)                                 O(1)                             O(N)

연결 리스트(unsorted linked list)                 O(1)                             O(N)

정렬된 배열(sorted array)                          O(N)                             O(1)

정렬된 연결 리스트(sorted linked list)           O(N)                            O(1)

힙(heap)                                                O(logN)                        O(logN)

 

heap방식이 worst case에도 O(logN)을 보장하기 때문에 일반적으로 heap으로 구현함.

 

heap은 complete binary tree. / 모든 노드에 저장된 값들은 자식 노드들의 값보다 크거나 같다. / 직접 연결된 자식-부모 노드 간의 크기만 비교하면 됨. / 힙으로 우선순위 큐를 구현할 때에는 노드에 저장된 값을 우선순위로 봄. / heap은 root 노드에 우선순위가 높은 데이터를 위치시키는 자료 구조.

 

□ peek() : peek()는 우선순위 큐에서 최대 우선순위 값을 반환함. 최대 우선순위 값(최대 힙)은 항상 root에 있으므로 root값 반환. 시간 복잡도 O(1)

 

□ enqueue() : enqueue()는 우선순위 큐(최대 힙)에 요소를 삽입하는 작업을 함. 

삽입 작업 순서 : 힙 끝에 새 요소 삽입 -> 부모 노드와 비교하여 힙 속성을 위배하는 경우 부모 노드와 값을 바꿈(re-adjust) -> 힙 속성이 유지될 때까지 2번 작업 반복. 시간 복잡도 O(logN)

 

□ heapify() : heapify()는 힙 속성을 유지하는 작업을 함. 위에서 아래로 내려가면서 작업.

max 힙에서 heapify 작업 : 자식 노드와 우선순위 비교 -> 만약 자식 노드 우선순위가 높다면 왼쪽 오른쪽 자식 중 가장 우선순위가 높은 노드와 교환 -> 힙 속성이 유지될 때까지 1,2번 과정 반복. 시간 복잡도 O(logN)

 

□ dequeue() : dequeue()는 우선 순위 큐에 최대 우선 순위 요소를 삭제하고 그 값을 반환함. 

삭제 작업 순서 : root 노드의 값 추출 -> heap 마지막 요소를 root 노드에 배치 -> 마지막 요소 제거 -> root 노드부터 heapify 수행. 시간 복잡도 O(logN)

 

사용하는 사례

CPU 스케줄링 / Dijkstra's shortest path algorithm / Prim's minimum spanning tree / 우선순위를 포함한 모든 queue / 운영체제에서 process 관리 / memory 관리 / 은행에서 VIP고객의 관리 등