C 언어로 우선순위 큐 구현: 이해와 코드 예제

C 언어에서 우선순위 큐(Priority Queue)는 데이터의 우선순위를 기준으로 정렬하여 효율적인 처리를 가능하게 하는 자료구조입니다. 본 기사에서는 우선순위 큐의 정의와 특성을 시작으로, 배열과 힙을 사용한 구현 방법, 응용 예제, 그리고 주요 연산의 시간 복잡도 분석까지 다룹니다. 이를 통해 우선순위 큐의 동작 원리와 C 언어로 구현하는 방법을 명확히 이해할 수 있습니다.

우선순위 큐란?

우선순위 큐(Priority Queue)는 데이터의 삽입 순서와 상관없이 각 요소의 우선순위를 기준으로 정렬되는 특수한 형태의 큐입니다.

우선순위 큐의 정의

일반적인 큐는 선입선출(FIFO) 방식을 따르지만, 우선순위 큐는 요소의 우선순위를 기준으로 가장 높은 우선순위를 가진 요소가 먼저 처리됩니다.

활용 예

작업 스케줄링: 운영 체제에서 높은 우선순위를 가진 작업을 먼저 처리.
데이터 패킷 전송: 네트워크에서 중요한 패킷을 우선적으로 전송.
다익스트라 알고리즘: 최단 경로를 찾기 위해 사용.

우선순위 큐는 다양한 상황에서 중요한 요소를 우선적으로 처리해야 할 때 유용하게 활용됩니다.

배열 기반 우선순위 큐 구현

배열을 활용한 우선순위 큐는 단순한 구현 방법으로, 초기 단계에서 우선순위 큐의 개념을 이해하기에 적합합니다.

배열 기반 우선순위 큐의 구조

배열을 사용하여 데이터를 저장하고, 삽입 시 우선순위에 따라 정렬하거나 삭제 시 우선순위가 가장 높은 요소를 선택합니다.

구현 방법

삽입: 데이터를 배열에 추가하며 우선순위를 고려하여 정렬.
삭제: 우선순위가 가장 높은 요소를 찾아 제거.

#include <stdio.h>
#define MAX 100

typedef struct {
    int data;
    int priority;
} Element;

Element queue[MAX];
int size = 0;

void insert(int data, int priority) {
    queue[size].data = data;
    queue[size].priority = priority;
    size++;
}

int deleteMax() {
    if (size == 0) {
        printf("Queue is empty!\n");
        return -1;
    }

    int maxIndex = 0;
    for (int i = 1; i < size; i++) {
        if (queue[i].priority > queue[maxIndex].priority) {
            maxIndex = i;
        }
    }

    int maxData = queue[maxIndex].data;
    for (int i = maxIndex; i < size - 1; i++) {
        queue[i] = queue[i + 1];
    }

    size--;
    return maxData;
}

int main() {
    insert(10, 2);
    insert(20, 1);
    insert(30, 3);

    printf("Deleted: %d\n", deleteMax()); // Output: 30
    printf("Deleted: %d\n", deleteMax()); // Output: 10

    return 0;
}

장단점

장점:
구현이 간단하며 직관적.
작은 데이터셋에서 효율적.
단점:
삽입 시 정렬 비용이 발생.
삭제 시 가장 높은 우선순위를 탐색하는 비용 증가.

배열 기반 구현은 학습 목적이나 단순한 작업에서 활용되지만, 성능이 중요한 경우 힙 자료구조 기반 구현으로 대체됩니다.

힙 기반 우선순위 큐 구현

힙 자료구조를 활용한 우선순위 큐는 배열 기반 구현에 비해 성능 면에서 더 효율적입니다. 특히 삽입과 삭제 연산에서 시간 복잡도를 줄일 수 있습니다.

힙이란 무엇인가

힙은 완전 이진 트리로 구성되며, 다음 두 가지 특성을 가집니다.

최대 힙(Max-Heap): 부모 노드가 자식 노드보다 크거나 같음.
최소 힙(Min-Heap): 부모 노드가 자식 노드보다 작거나 같음.

우선순위 큐에서는 일반적으로 최대 힙을 사용하여 높은 우선순위를 가진 요소를 빠르게 추출합니다.

힙 기반 구현

아래는 최대 힙을 활용한 우선순위 큐 구현 예제입니다.

#include <stdio.h>
#define MAX 100

int heap[MAX];
int heapSize = 0;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void insert(int value) {
    heap[heapSize] = value;
    int current = heapSize;

    // 힙 속성을 유지하기 위해 부모와 비교 후 교환
    while (current > 0 && heap[current] > heap[(current - 1) / 2]) {
        swap(&heap[current], &heap[(current - 1) / 2]);
        current = (current - 1) / 2;
    }

    heapSize++;
}

int deleteMax() {
    if (heapSize == 0) {
        printf("Heap is empty!\n");
        return -1;
    }

    int maxValue = heap[0];
    heap[0] = heap[--heapSize];

    // 힙 속성을 유지하기 위해 자식들과 비교 후 교환
    int current = 0;
    while (1) {
        int left = 2 * current + 1;
        int right = 2 * current + 2;
        int largest = current;

        if (left < heapSize && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < heapSize && heap[right] > heap[largest]) {
            largest = right;
        }
        if (largest == current) break;

        swap(&heap[current], &heap[largest]);
        current = largest;
    }

    return maxValue;
}

int main() {
    insert(10);
    insert(30);
    insert(20);

    printf("Deleted: %d\n", deleteMax()); // Output: 30
    printf("Deleted: %d\n", deleteMax()); // Output: 20

    return 0;
}

장단점

장점:
삽입 및 삭제 연산이 O(log N)의 시간 복잡도를 가짐.
대규모 데이터 처리에 적합.
단점:
배열 기반보다 구현이 복잡.
초기 힙 구조 생성 비용 발생.

힙 기반 우선순위 큐는 성능이 중요한 애플리케이션에서 자주 사용되며, 작업 스케줄러나 알고리즘 최적화에서 매우 유용합니다.

동적 메모리 관리와 구현

동적 메모리를 활용하면 우선순위 큐가 가변 크기의 데이터를 처리할 수 있어 유연성이 증가합니다. 특히, 동적 메모리를 사용하면 배열 크기의 제한을 극복하고, 힙 기반 우선순위 큐의 크기를 동적으로 조정할 수 있습니다.

동적 메모리 할당

동적 메모리 관리는 C 언어에서 malloc과 free를 사용하여 구현됩니다. 이 방법을 사용하면 필요에 따라 메모리를 할당하고 해제하여 효율적인 메모리 사용이 가능합니다.

동적 메모리를 사용하는 힙 기반 우선순위 큐 구현

아래는 동적 메모리를 활용한 힙 기반 우선순위 큐 구현입니다.

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

typedef struct {
    int *data;
    int size;
    int capacity;
} PriorityQueue;

PriorityQueue* createQueue(int capacity) {
    PriorityQueue *pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    pq->data = (int*)malloc(capacity * sizeof(int));
    pq->size = 0;
    pq->capacity = capacity;
    return pq;
}

void freeQueue(PriorityQueue *pq) {
    free(pq->data);
    free(pq);
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void resizeQueue(PriorityQueue *pq) {
    pq->capacity *= 2;
    pq->data = (int*)realloc(pq->data, pq->capacity * sizeof(int));
}

void insert(PriorityQueue *pq, int value) {
    if (pq->size == pq->capacity) {
        resizeQueue(pq);
    }

    pq->data[pq->size] = value;
    int current = pq->size;

    while (current > 0 && pq->data[current] > pq->data[(current - 1) / 2]) {
        swap(&pq->data[current], &pq->data[(current - 1) / 2]);
        current = (current - 1) / 2;
    }

    pq->size++;
}

int deleteMax(PriorityQueue *pq) {
    if (pq->size == 0) {
        printf("Queue is empty!\n");
        return -1;
    }

    int maxValue = pq->data[0];
    pq->data[0] = pq->data[--pq->size];

    int current = 0;
    while (1) {
        int left = 2 * current + 1;
        int right = 2 * current + 2;
        int largest = current;

        if (left < pq->size && pq->data[left] > pq->data[largest]) {
            largest = left;
        }
        if (right < pq->size && pq->data[right] > pq->data[largest]) {
            largest = right;
        }
        if (largest == current) break;

        swap(&pq->data[current], &pq->data[largest]);
        current = largest;
    }

    return maxValue;
}

int main() {
    PriorityQueue *pq = createQueue(4);

    insert(pq, 10);
    insert(pq, 30);
    insert(pq, 20);
    insert(pq, 40);

    printf("Deleted: %d\n", deleteMax(pq)); // Output: 40
    printf("Deleted: %d\n", deleteMax(pq)); // Output: 30

    freeQueue(pq);
    return 0;
}

장단점

장점:
데이터 크기의 유연한 처리 가능.
큐의 크기를 초과하지 않아도 됨.
단점:
메모리 할당 및 해제 시 성능 비용 발생.
malloc과 free를 적절히 사용하지 않으면 메모리 누수 가능성.

동적 메모리를 활용한 우선순위 큐는 대규모 데이터나 가변적인 입력을 처리하는 경우 매우 유용하며, 메모리 사용 효율성을 높이는 데 기여합니다.

시간 복잡도 분석

우선순위 큐의 성능은 주요 연산인 삽입과 삭제의 시간 복잡도에 따라 결정됩니다. 여기서는 배열 기반과 힙 기반 구현의 시간 복잡도를 비교합니다.

배열 기반 우선순위 큐

삽입

데이터 삽입 시 정렬된 위치를 유지하려면 배열의 요소를 이동해야 합니다.
최악의 경우 시간 복잡도는 O(N)입니다.

삭제(최대값 또는 최소값 제거)

배열에서 가장 높은 우선순위를 가진 요소를 탐색해야 합니다.
시간 복잡도는 O(N)입니다.

힙 기반 우선순위 큐

삽입

힙에 요소를 삽입한 후 힙 속성을 유지하기 위해 상향 이동을 수행합니다.
시간 복잡도는 O(log N)입니다.

삭제(최대값 또는 최소값 제거)

힙에서 루트 노드(최대값 또는 최소값)를 제거하고 힙 속성을 유지하기 위해 하향 이동을 수행합니다.
시간 복잡도는 O(log N)입니다.

비교

연산	배열 기반 구현	힙 기반 구현
삽입	O(N)	O(log N)
삭제	O(N)	O(log N)

결론

힙 기반 우선순위 큐는 삽입 및 삭제 연산에서 배열 기반에 비해 더 효율적입니다. 이는 특히 대규모 데이터셋이나 반복적인 연산이 필요한 작업에서 성능 차이를 크게 만듭니다. 따라서, 실용적인 구현에서는 힙 기반 우선순위 큐가 선호됩니다.

시간 복잡도에 대한 이해를 통해 우선순위 큐를 적절히 선택하고, 구현에서 성능을 최적화할 수 있습니다.

응용 예제: 작업 스케줄러

우선순위 큐는 운영 체제나 소프트웨어 애플리케이션에서 작업의 우선순위를 기반으로 스케줄링할 때 매우 유용합니다. 여기서는 힙 기반 우선순위 큐를 사용하여 작업 스케줄러를 구현하는 예제를 소개합니다.

작업 스케줄러의 개념

작업 스케줄러는 여러 작업 중 우선순위가 높은 작업을 먼저 처리하도록 설계됩니다. 각 작업에는 다음과 같은 정보가 포함됩니다.

작업 이름
작업 우선순위

작업 스케줄러 구현

아래는 작업 스케줄러를 구현한 코드입니다.

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

typedef struct {
    char name[50];
    int priority;
} Task;

typedef struct {
    Task *tasks;
    int size;
    int capacity;
} PriorityQueue;

PriorityQueue* createQueue(int capacity) {
    PriorityQueue *pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    pq->tasks = (Task*)malloc(capacity * sizeof(Task));
    pq->size = 0;
    pq->capacity = capacity;
    return pq;
}

void freeQueue(PriorityQueue *pq) {
    free(pq->tasks);
    free(pq);
}

void swap(Task *a, Task *b) {
    Task temp = *a;
    *a = *b;
    *b = temp;
}

void resizeQueue(PriorityQueue *pq) {
    pq->capacity *= 2;
    pq->tasks = (Task*)realloc(pq->tasks, pq->capacity * sizeof(Task));
}

void insert(PriorityQueue *pq, const char *name, int priority) {
    if (pq->size == pq->capacity) {
        resizeQueue(pq);
    }

    strcpy(pq->tasks[pq->size].name, name);
    pq->tasks[pq->size].priority = priority;
    int current = pq->size;

    while (current > 0 && pq->tasks[current].priority > pq->tasks[(current - 1) / 2].priority) {
        swap(&pq->tasks[current], &pq->tasks[(current - 1) / 2]);
        current = (current - 1) / 2;
    }

    pq->size++;
}

Task deleteMax(PriorityQueue *pq) {
    if (pq->size == 0) {
        printf("Queue is empty!\n");
        Task empty = {"", -1};
        return empty;
    }

    Task maxTask = pq->tasks[0];
    pq->tasks[0] = pq->tasks[--pq->size];

    int current = 0;
    while (1) {
        int left = 2 * current + 1;
        int right = 2 * current + 2;
        int largest = current;

        if (left < pq->size && pq->tasks[left].priority > pq->tasks[largest].priority) {
            largest = left;
        }
        if (right < pq->size && pq->tasks[right].priority > pq->tasks[largest].priority) {
            largest = right;
        }
        if (largest == current) break;

        swap(&pq->tasks[current], &pq->tasks[largest]);
        current = largest;
    }

    return maxTask;
}

int main() {
    PriorityQueue *pq = createQueue(4);

    insert(pq, "Task A", 3);
    insert(pq, "Task B", 5);
    insert(pq, "Task C", 1);
    insert(pq, "Task D", 4);

    printf("Processing: %s\n", deleteMax(pq).name); // Output: Task B
    printf("Processing: %s\n", deleteMax(pq).name); // Output: Task D
    printf("Processing: %s\n", deleteMax(pq).name); // Output: Task A

    freeQueue(pq);
    return 0;
}

작업 스케줄러의 주요 기능

작업 추가: 새로운 작업을 추가하며 우선순위를 고려.
작업 처리: 우선순위가 높은 작업부터 순서대로 처리.

응용 가능성

운영 체제 스케줄러: CPU 작업 스케줄링에 활용.
네트워크 트래픽 관리: 중요 패킷 우선 전송.
프린터 대기열 관리: 우선순위가 높은 인쇄 작업 처리.

우선순위 큐 기반 작업 스케줄러는 실제 시스템에서 중요한 작업을 효율적으로 관리하고 처리하는 데 기여합니다.

요약

본 기사에서는 C 언어를 활용하여 우선순위 큐를 구현하는 다양한 방법과 그 활용 예를 살펴보았습니다. 배열 기반 구현의 단순함과 힙 기반 구현의 효율성을 비교하고, 동적 메모리 관리 기법을 통해 유연성을 더했습니다. 또한, 작업 스케줄러 예제를 통해 우선순위 큐의 실질적인 응용 사례를 제시했습니다. 이를 통해 우선순위 큐의 기본 개념부터 고급 구현 방법까지 체계적으로 이해할 수 있습니다.