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

1. 우선순위 큐란?

  우선순위 큐(Priority Queue)는 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리되는 자료구조이다.

  큐는 선형 자료구조이고, 우선순위 큐는 비 선형 자료구조이다. 우선순위 큐는 자료가 들어온 순서와 상관 없이 미리 정한 우선순위대로 나간다.

  주로 정의된 우선 순위를 heap condition으로 가지는 heap을 이용해 구현된다. 그 이유는 시간 복잡도와 관련이 있는데, 배열 기반 데이터 삽입의 시간 복잡도는 O(n) 이고 배열 기반 데이터 삭제의 시간 복잡도는 O(1)이다. 또 연결 리스트 기반 데이터 삽입과 삭제의 시간 복잡도도 위와 같다. 하지만 힙 기반 데이터 삽입과 삭제의 시간 복잡도는 각각 O(logn)이다. 따라서 힙을 먼저 공부해야 한다. 

 

🔍힙이란?

jina-developer.tistory.com/98

자료구조 - 힙 (Heap)

2. 특징

1) 우선순위 큐의 연산

- 큐에 데이터를 우선순위를 지정하여 추가한다.

- 큐에서 가장 우선순위가 높은 데이터를 제거하고 반환한다.

 

2) heap을 통해 구현하는 연산

- heap에 데이터를 우선순위를 지정해 삽입연산을 수행한다.

- heap의 삭제연산을 수행하고 삭제된 데이터를 반환한다.

 

[예시문제]

주어진 N(2<= N <=100)개의 수를 작은 숫자가 높은 우선순위를 갖는 Priority Queue에 저장하고,
우선 순위가 높은 숫자부터 차례대로 출력하시오.
(입력에는 오류가 없다고 가정)

 

[입력]

테스트 케이스 수

입력 수

입력 데이터

 

[Reference Code]

#include <stdio.h>
 
#define MAX_SIZE 100
 
int heap[MAX_SIZE];
int heapSize = 0;
 
void heapInit(void)
{
    heapSize = 0;
}
 
int heapPush(int value)
{
    if (heapSize + 1 > MAX_SIZE)
    {
        printf("queue is full!");
        return 0;
    }
 
    heap[heapSize] = value;
 
    int current = heapSize;
    while (current > 0 && heap[current] < heap[(current - 1) / 2]) //삽입 노드를 부모 노드와 비교 
    { //첫번째 노드가 아니고 부모보다 작다면
        int temp = heap[(current - 1) / 2]; //Swap
        heap[(current - 1) / 2] = heap[current];
        heap[current] = temp;
        current = (current - 1) / 2;
    }
 
    heapSize = heapSize + 1;
 
    return 1;
}
 
int heapPop(int *value)
{
    if (heapSize <= 0)
    {
        return -1;
    }
 
    *value = heap[0];
    heapSize = heapSize - 1;
 
    heap[0] = heap[heapSize]; //마지막 노드의 값을 첫번째로 옮김
 
    int current = 0;
    while (current * 2 + 1 < heapSize)
    {
        int child;
        if (current * 2 + 2 == heapSize)
        {
            child = current * 2 + 1;
        }
        else
        {
            child = heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;
        }
 
        if (heap[current] < heap[child])
        {
            break;
        }
 
        int temp = heap[current];
        heap[current] = heap[child];
        heap[child] = temp;
 
        current = child;
    }
    return 1;
}
 
int main(int argc, char* argv[])
{
    int T, N;
 
    scanf("%d", &T);
 
    for (int test_case = 1; test_case <= T; test_case++)
    {
        scanf("%d", &N);
         
        heapInit();
         
        for (int i = 0; i < N; i++)
        {
            int value;
            scanf("%d", &value);
            heapPush(value);
        }
 
        printf("#%d ", test_case);
 
        for (int i = 0; i < N; i++)
        {
            int value;
            heapPop(&value);
            printf("%d ", value);
        }
        printf("\n");
    }
    return 0;
}

최대/최소 힙으로 우선순위 큐를 구현하면 된다. 위 예제에서는 가장 작은 숫자가 높은 우선순위를 가져야하기 때문에, 최소 힙으로 구현하면 된다.