우선순위 큐는 일반적인 큐와 달리 데이터의 삽입 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. 각 요소는 우선순위 값을 가지며, 이 값에 따라 큐에서 빠져나오는 순서가 결정된다.

우선순위 큐의 특징

• 가장 높은(또는 가장 낮은) 우선순위를 가진 요소가 항상 먼저 처리된다.
• 힙(Heap) 자료구조를 사용하여 효율적으로 구현할 수 있다.
• 시간 복잡도: 삽입 및 삭제 연산 모두 O(log n)이다.
• Dijkstra 알고리즘, Prim 알고리즘, 허프만 코딩 등 다양한 알고리즘에 활용된다.
• 힙큐라고도 한다.

우선순위 큐의 구현 방법

우선순위 큐는 다양한 방법으로 구현할 수 있지만, 가장 효율적인 방법은 이진 힙(Binary Heap)을 사용하는 것이다. 여기서는 C언어를 사용하여 최대 힙(Max Heap) 기반의 우선순위 큐를 구현해보겠다.

C언어로 구현한 우선순위 큐

1. 필요한 헤더 및 구조체 정의

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 우선순위 큐의 최대 크기 정의
#define MAX_SIZE 100

// 우선순위 큐 구조체 정의
typedef struct {
    int heap[MAX_SIZE];
    int size;
} PriorityQueue;

2. 초기화 함수 (initialize)

// 우선순위 큐 초기화
void initialize(PriorityQueue* pq) {
    pq->size = 0;
}

우선순위 큐를 사용하기 전에 초기화하는 함수이다. 큐의 크기를 0으로 설정한다.

3. 힙 조정 함수 (swap, heapify)

// 두 노드 값을 교환하는 함수
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 최대 힙 속성을 유지하기 위해 힙을 재구성하는 함수
void heapifyUp(PriorityQueue* pq, int index) {
    int parent = (index - 1) / 2;
    
    if (index > 0 && pq->heap[parent] < pq->heap[index]) {
        swap(&pq->heap[parent], &pq->heap[index]);
        heapifyUp(pq, parent);
    }
}

void heapifyDown(PriorityQueue* pq, int index) {
    int largest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    
    if (left < pq->size && pq->heap[left] > pq->heap[largest]) {
        largest = left;
    }
    
    if (right < pq->size && pq->heap[right] > pq->heap[largest]) {
        largest = right;
    }
    
    if (largest != index) {
        swap(&pq->heap[index], &pq->heap[largest]);
        heapifyDown(pq, largest);
    }
}

heapifyUp은 요소가 삽입된 후 그 요소가 부모 노드보다 우선순위가 높을 경우 위로 이동시키는 함수이다.

heapifyDown은 루트 노드가 제거된 후 마지막 요소가 루트로 이동했을 때, 이를 적절한 위치로 내려보내는 함수이다.

4. 삽입 함수 (enqueue)