1. 우선순위 큐?

우선순위 큐란,

기존의 FIFO(First In First Out) 형식의 자료구조였던 큐에서,

우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

Cf) 우선순위 흐름으로 진행되는 네트워크 트래픽 제어, 작업 스케쥴링 등의 경우에 많이 사용한다.

우선순위 큐는 일반적으로 힙을 이용하여 구현한다.

힙 이외에도 '배열', '연결 리스트' 등의 방법이 있지만 대략적으로 시뮬레이션을 해보거나 시간 복잡도를 따져봤을 때 힙을 사용하는 연산이 가장 빠르기 때문이다.

2. 힙?

더미라는 뜻이다.

완전이진트리 형태이다.

중복된 값이 허용된다.

종류로 최대 힙(Max Heap), 최소 힙(Min Heap)이 있다.

최대 힙(Max Heap)

-key(부모노드) ≥ key(자식노드) 한 완전이진트리이다.

최소 힙(Min Heap)

-key(부모노드) ≤ key(자식노드) 한 완전이진트리이다.

부모노드와 자식노드의 관계

-왼쪽 자식노드의 index = (부모노드의 index)*2

-오른쪽 자식노드의 index = (부모노드의 index)*2 + 1

-부모노드의 index = (자식노드의 index)/2

3. C++에서 구현? (STL)

#include <iostream>
#include <queue>
#include <tuple>
#include <string>
#include <fstream>

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()

힙 속성을 유지하는 작업을 합니다. 위에서 아래로 내려가면서 작업을 합니다. max heap에서 heapify의 작업은 다음과 같습니다.

1. 자식 노드와 우선순위를 비교합니다.

2. 만약 자식 노드 우선순위가 높다면 왼쪽 오른쪽 자식 중 가장 우선순위가 높은 노드와 교환합니다.

3. 힙 속성이 유지될 때까지 1, 2번 작업을 반복합니다.

-다음 그림은 루트 노드에서 max_heapify()를 수행하는 예입니다.

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()

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;
}

Heap_Sort(힙 정렬 알고리즘)

1. Build Max_Heap

2. Find max element A[i]

3. Swap element A[n] and A[i]

4. Discard node n

5. go to step 2

<참고자료>(감사합니다.)
C++로 쉽게 풀어쓴 자료구조, 천인국, 생능출판사
Suyeon's Blog(Tistory), https://suyeon96.tistory.com/31
yoongrammer(Tistory), https://yoongrammer.tistory.com/81