우선 순위 큐 - Priority Queue

속성

1. 모든 항목에는 우선 순위가 있다

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

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

 

4 → 8 → 2 순으로 데이터가 들어간다고 했을 때 큐와 우선순위 큐의 처리 순서는 다음과 같다.

(여기서 높은 값이 높은 우선순위를 갖는다고 가정.)

input : 4 → 8 → 2

큐 : 4 → 8 → 2

우선순위 큐 : 8 → 4 → 2

기본 동작

• enqueue()- queue에 새 요소를 삽입.
• dequeue() - queue에서 최대 우선 순위 요소를 삭제하고 그 값을 반환.
• peek() - queue에서 최대 우선순위 요소를 반환.

구현

 

힙 방식이 최악에 경우라도 O(logN)을 보장하기 때문에 일반적으로 힙을 가지고 구현을 한다.

struct node {
  int data;
  int priority;
}

 

• 배열에는 우선순위만 들어있다.
• 값이 클 수록 우선순위가 높다. (최대 힙)
• size변수는 전역변수이며 힙에 있는 요소수를 나타낸다.
• 루트 노드는 인덱스 1에 위치한다.

peek() / 시간 복잡도 : O(1)

peek()은 우선순위 큐에서 최대 우선순위 값을 반환한다.

최대 우선순위 값(최대 힙)은 항상 루트에 있으므로 루트 값을 반환한다.

int peek(int arr[]) {
  return arr[1];
}

enqueue() / 시간 복잡도 : O(logN)

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

삽입 작업은 다음과 같다.

1. 힙 끝에 새 요소를 삽입한다.
2. 부모 노드와 비교하여 힙 속성을 위배하는 경우 부모 노드와 값을 바꾼다.
3. 힙 속성이 유지될 때까지 2번 작업을 반복한다.

void enqueue(int arr[], int val)
{
  int i = 0; 
  if (size == MAX_LEN) { // 배열에 공간이 없으면 실패
    printf("Overflow: Could not insertKey\n");
  }
  
  // 힙 끝에 요소 삽입.
  size ++;
  i = size;
  arr[i]= val;

  // 우선순위가 부모 노드가 더 작다면 교환하고 부모 노드부터 다시 비교, 힙속성을 유지할 때까지 반복함.
  while(i > 1 && arr[i/2] < arr[i]) {
    swap(arr[i/2], arr[i]);
    i = i/2;
  }
}

heapify() / 시간 복잡도 : O(logN)

heapify는 위에서 아래로 내려가면서 힙 속성을 유지하는 작업을 한다.

max heap에서 heapify의 작업은 다음과 같다.

1. 자식 노드와 우선순위를 비교한다.
2. 만약 자식 노드 우선순위가 높다면 왼쪽 오른쪽 자식 중 가장 우선순위가 높은 노드와 교환한다.
3. 힙 속성이 유지 될 때까지 1,2번 과정을 반복한다.

void max_heapify (int arr[], int i)
{
  int largest = i;  
  int left = 2*i              //left child
  int right = 2*i +1          //right child
  
  // 현재 요소 i와 자식 노드의 값을 비교
  if(left <= size && arr[left] > arr[i] )
    largest = left;  
  if(right <= size && arr[right] > arr[largest] )
    largest = right;
  
  // 자식 노드의 값이 더 크다면 교환하고 교환된 자식 노드부터 heapify 진행
  if(largest != i ) {
    swap (arr[i] , arr[largest]);
    max_heapify (h, largest);
  } 
}

dequeue() / 시간 복잡도 : O(logN)

dequeue()는 우선 순위 큐(최대 힙)에 최대 우선순위 요소를 삭제하고 그 값을 반환하는 작업을 한다.

삭제 작업은 다음과 같다.

1. 루트 노드의 값을 추출한다.
2. heap 마지막 요소를 루트 노드에 배치한다.
3. 마지막 요소는 제거한다.
4. 루트 노드부터 heapify를 수행한다.

int dequeue (int arr[]) {
  if(size == 0) {
    printf("empty\n");
  }
  
  // 루트 노드 값을 리턴값에 저장한 뒤, 마지막 요소를 루트노드에 배치함
  Node max = arr[1];
  arr[1] = arr[size];
  size --;

  // 루트 노드부터 heapify 수행
  max_heapify(arr, 1);
  
  return max;

사용 사례

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

 

[자료구조] 우선순위 큐 (Priority Queue) 개념 및 구현 (tistory.com)