(Data_Structure) Priority Queue

Priority Queue는 각 요소가 특정 우선 순위를 가지고 있는 큐이다.

높은 우선순위를 가진 data가 낮은 우선 순위를 가진 data보다 먼저 처리된다.

 

Priority Queue의 ADT를 보면 

insert(): 우선순위 큐에 새로운 data를 추가

deleteMax() or deleteMin() : 우선순위가 가장 높은(낮은) 항목을 제거

getMax() or getMin(): 우선순위가 가장 높은(낮은) 항목을 return

isEmpty() : 비어있는지 확인

size() : 우선순위 큐에 저장된 data의 개수를 return

clear() : 우선순위 큐의 모든 data 제거

 

Priority Queue 같은 경우 작업 스케줄링, 그래프 알고리즘, 네트워크 라우팅 등에서 활용된다.

 

구현 방식으로는 이진 힙(Binary Heap), 이진 탐색 트리(Binary Search Tree),

피보나치 힙(Fibonacci Heap) 등 여러가지 구조를 사용하여 구현할 수 있다.

 

예시) sort하는 pseudocode이다.

Algorithm PQ-Sort(S,C)
  Input sequence S, Comparator C for the elements of S
  Output sequence S sorted in increasing order according to C
  P <- priority queue with comparator C
  while ￢S.empty()
    e <- S.front();S.eraseFront()
    P.insert(e,Φ)
  while ￢P.empty()
    e <- P.removeMin()
    S.insertBack(e)