[자료구조] 우선순위 큐(Priority Queue)

우선순위 큐(Priority)

• 순서에 상관없이 우선수위가 높은 데이터가 먼저 나가는 형태의 자료구조
• 우선순위 대기열이라고도 함
• 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조
• 일반적으로 힙(Heap)을 사용하여 구현
  • 모든 항목에는 우선순위가 있음
  • 우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 큐에서 제외
  • 두 요소의 우선순위가 같은 경우 큐의 순서에 따라 제공

우선순위 큐 구현 방법

• 배열, 연결리스트, 힙을 이용하여 구현 가능

구현 방법	삽입 (enqueue)	삭제 (denqueue)
배열 (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)

 

우선순위 큐 ADT

객체

• 우선순위를 가진 요소들의 모음

연산

• insert(x) : 우선순위 큐에 요소 x 추가
• remove() : 우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 반환
• find() : 우선순위 큐에서 가장 우선순위가 높은 요소를 반환

우선순위 큐의 동작

• peek()
  • 우선순위 큐에서 최대 우선순위 값을 반환
  • 최대 우선순위 값(최대 힙)은 항상 루트에 있으므로 루트 값을 반환
• enqueue()
  • 우선순위 큐(최대 힙)에 요소를 삽입
• heapify()
  • 힙 속성을 유지하며, 위에서 아래로 내려가면서 작업
    1. 자식 노드와 우선순위를 비교
    2. 만약 자식 노드 우선순위가 높다면 왼쪽 오른쪽 자식 중 가장 우선순위가 높은 노드와 교환
    3. 힙 속성이 유지될 때까지 1,2번 과정을 반복
• dequeue()
  • 우선순위 큐(최대 힙)에 최대 우선순위 요소를 삭제하고 그 값을 반환하는 작업

우선순위 큐의 사용사례

1. CPU 스케줄링
2. Dijkstra's shortest path algorithm, Prim's Mininum Spanning tree
3. 우선순위를 포함한 모든 queue 응용