C언어로 배우는 힙 자료구조와 우선순위 큐 구현 방법

힙(Heap) 자료구조와 우선순위 큐는 컴퓨터 과학에서 매우 중요한 역할을 합니다. 힙은 효율적인 데이터 관리와 정렬을 가능하게 하며, 우선순위 큐는 이를 활용해 특정 기준에 따라 데이터 처리를 최적화합니다. C 언어를 통해 힙 자료구조의 동작 원리를 이해하고, 이를 기반으로 우선순위 큐를 구현하는 방법을 학습해 보겠습니다. 본 기사는 이론적 배경부터 실제 코드 구현, 실용적 활용 사례까지 다룹니다.

힙(Heap)의 개념과 기본 원리

힙(Heap)은 트리 기반의 자료구조로, 일반적으로 최대 힙(Max-Heap)과 최소 힙(Min-Heap)으로 구분됩니다. 이진 힙(Binary Heap)은 완전 이진 트리의 형태를 가지며, 부모 노드와 자식 노드 간의 특정 관계를 유지합니다.

힙의 특징

완전 이진 트리: 모든 레벨이 꽉 차 있으며, 마지막 레벨만 왼쪽부터 채워지는 특성을 가집니다.
힙 속성:

최대 힙: 부모 노드의 값이 자식 노드의 값보다 크거나 같습니다.
최소 힙: 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.

힙의 주요 연산

삽입(Insertion): 새로운 요소를 힙에 추가하고, 힙 속성을 유지하기 위해 요소를 상향 이동합니다(Heapify-Up).
삭제(Deletion): 일반적으로 루트 노드를 삭제하며, 힙 속성을 유지하기 위해 요소를 하향 이동합니다(Heapify-Down).

힙의 응용

힙은 우선순위 큐 구현, 힙 정렬, 그리고 Dijkstra 알고리즘과 같은 최단 경로 탐색 문제에서 널리 사용됩니다. C 언어로 이러한 연산들을 효율적으로 구현함으로써 힙 자료구조의 활용 가치를 이해할 수 있습니다.

힙의 구현 방법

C 언어로 힙 자료구조를 구현하려면 배열을 기반으로 하는 방식이 일반적입니다. 힙은 완전 이진 트리의 구조를 가지므로 배열 인덱스를 이용해 부모와 자식 간의 관계를 나타낼 수 있습니다.

배열 기반 힙 표현

배열 인덱스를 사용해 부모와 자식 노드를 연결합니다:

부모 노드: i
왼쪽 자식: 2 * i + 1
오른쪽 자식: 2 * i + 2

힙의 기본 코드 구조

다음은 최소 힙을 구현하는 기본 코드 예제입니다:

#include <stdio.h>
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int size;
} MinHeap;

// 초기화
void initHeap(MinHeap *heap) {
    heap->size = 0;
}

// 삽입 연산
void insert(MinHeap *heap, int value) {
    if (heap->size >= MAX_SIZE) {
        printf("Heap overflow\n");
        return;
    }
    int i = heap->size;
    heap->data[i] = value;
    heap->size++;

    // Heapify-Up
    while (i > 0 && heap->data[(i - 1) / 2] > heap->data[i]) {
        int temp = heap->data[i];
        heap->data[i] = heap->data[(i - 1) / 2];
        heap->data[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
}

// 삭제 연산
int deleteMin(MinHeap *heap) {
    if (heap->size == 0) {
        printf("Heap underflow\n");
        return -1;
    }
    int min = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;

    // Heapify-Down
    int i = 0;
    while (2 * i + 1 < heap->size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = left;

        if (right < heap->size && heap->data[right] < heap->data[left])
            smallest = right;

        if (heap->data[i] <= heap->data[smallest])
            break;

        int temp = heap->data[i];
        heap->data[i] = heap->data[smallest];
        heap->data[smallest] = temp;

        i = smallest;
    }
    return min;
}

// 테스트 코드
int main() {
    MinHeap heap;
    initHeap(&heap);

    insert(&heap, 10);
    insert(&heap, 20);
    insert(&heap, 5);
    printf("Deleted: %d\n", deleteMin(&heap)); // 5 출력

    return 0;
}

설명

initHeap: 힙을 초기화합니다.
insert: 새로운 값을 힙에 삽입하며, 힙 속성을 유지하기 위해 상향 이동합니다(Heapify-Up).
deleteMin: 최소 힙에서 최솟값(루트 노드)을 삭제하며, 힙 속성을 유지하기 위해 하향 이동합니다(Heapify-Down).

이 코드를 기반으로 힙의 기본 동작을 구현할 수 있으며, 다양한 자료구조 문제에 응용할 수 있습니다.

우선순위 큐란 무엇인가

우선순위 큐(Priority Queue)는 데이터를 우선순위에 따라 관리하고 처리하는 특수한 형태의 큐입니다. 일반적인 큐가 “선입선출(FIFO)” 원칙을 따르는 반면, 우선순위 큐는 데이터의 우선순위에 따라 요소가 삽입 및 삭제됩니다.

우선순위 큐의 정의

우선순위 큐는 다음과 같은 특징을 가집니다:

우선순위 기반 정렬: 높은 우선순위를 가진 데이터가 먼저 처리됩니다.
추상 자료형: 사용자는 큐의 내부 구현에 대한 상세 정보를 알 필요 없이, 제공된 연산만 사용해 데이터를 관리합니다.

우선순위 큐의 활용 사례

우선순위 큐는 다양한 실세계 문제를 효율적으로 해결하는 데 사용됩니다:

네트워크 라우팅: 네트워크에서 최단 경로를 찾는 Dijkstra 알고리즘에 활용됩니다.
이벤트 관리: 실시간 시스템에서 이벤트를 우선순위에 따라 처리합니다.
작업 스케줄링: 운영 체제에서 프로세스를 우선순위 기반으로 스케줄링합니다.

우선순위 큐의 구현 방식

우선순위 큐는 여러 가지 방식으로 구현될 수 있습니다:

배열(Array): 단순하지만 비효율적인 방식으로, 삽입은 빠르지만 정렬된 데이터를 검색하는 데 시간이 오래 걸립니다.
정렬된 리스트(Sorted List): 정렬된 상태로 유지되므로 검색은 빠르지만 삽입 시 추가 작업이 필요합니다.
힙(Heap): 효율적이고 일반적으로 사용되는 방식으로, 삽입과 삭제가 모두 O(log n)의 시간 복잡도를 가집니다.

힙을 사용하는 이유

힙을 이용한 우선순위 큐는 다음과 같은 이유로 가장 널리 사용됩니다:

삽입과 삭제가 빠릅니다.
메모리 사용이 효율적입니다.
트리 구조를 유지하므로 정렬이 자동으로 이루어집니다.

우선순위 큐의 원리를 이해하면, 다양한 알고리즘 문제에서 이를 활용해 더 효율적인 해법을 설계할 수 있습니다.

힙을 활용한 우선순위 큐 구현

힙 자료구조는 우선순위 큐를 구현하는 데 가장 적합한 방식 중 하나입니다. 최대 힙(Max-Heap) 또는 최소 힙(Min-Heap)을 이용하여 우선순위 큐의 삽입 및 삭제 연산을 효율적으로 처리할 수 있습니다.

우선순위 큐 구현의 기본 원리

삽입(Insertion): 새로운 요소를 힙에 추가한 후, 힙 속성을 유지하기 위해 상향 이동(Heapify-Up)을 수행합니다.
삭제(Deletion): 최우선순위의 요소(루트 노드)를 제거한 후, 힙 속성을 유지하기 위해 하향 이동(Heapify-Down)을 수행합니다.

C 언어를 이용한 우선순위 큐 구현

다음은 최소 힙을 기반으로 우선순위 큐를 구현하는 코드 예제입니다:

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int size;
} PriorityQueue;

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

// 요소 삽입
void enqueue(PriorityQueue *pq, int value) {
    if (pq->size >= MAX_SIZE) {
        printf("Priority Queue overflow\n");
        return;
    }
    int i = pq->size;
    pq->data[i] = value;
    pq->size++;

    // Heapify-Up
    while (i > 0 && pq->data[(i - 1) / 2] > pq->data[i]) {
        int temp = pq->data[i];
        pq->data[i] = pq->data[(i - 1) / 2];
        pq->data[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
}

// 요소 제거
int dequeue(PriorityQueue *pq) {
    if (pq->size == 0) {
        printf("Priority Queue underflow\n");
        return -1;
    }
    int min = pq->data[0];
    pq->data[0] = pq->data[pq->size - 1];
    pq->size--;

    // Heapify-Down
    int i = 0;
    while (2 * i + 1 < pq->size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = left;

        if (right < pq->size && pq->data[right] < pq->data[left])
            smallest = right;

        if (pq->data[i] <= pq->data[smallest])
            break;

        int temp = pq->data[i];
        pq->data[i] = pq->data[smallest];
        pq->data[smallest] = temp;

        i = smallest;
    }
    return min;
}

// 테스트 코드
int main() {
    PriorityQueue pq;
    initQueue(&pq);

    enqueue(&pq, 15);
    enqueue(&pq, 10);
    enqueue(&pq, 20);
    enqueue(&pq, 5);

    printf("Dequeued: %d\n", dequeue(&pq)); // 5 출력
    printf("Dequeued: %d\n", dequeue(&pq)); // 10 출력

    return 0;
}

코드 설명

initQueue: 우선순위 큐를 초기화합니다.
enqueue: 값을 큐에 삽입하며, 힙 속성을 유지하기 위해 상향 이동(Heapify-Up)을 수행합니다.
dequeue: 우선순위가 가장 높은 요소를 제거하며, 힙 속성을 유지하기 위해 하향 이동(Heapify-Down)을 수행합니다.

구현의 효율성

삽입과 삭제 연산 모두 시간 복잡도는 O(log n)입니다.
완전 이진 트리 형태를 유지하므로 메모리 사용이 효율적입니다.

힙을 기반으로 우선순위 큐를 구현하면 데이터 관리와 처리 효율성을 극대화할 수 있습니다.

삽입 연산과 삭제 연산

힙에서 삽입 연산과 삭제 연산은 힙 속성을 유지하는 데 핵심적인 작업입니다. 이 두 연산은 힙 자료구조와 우선순위 큐를 효율적으로 작동하게 하는 기본 원리를 포함하고 있습니다.

삽입 연산 (Heap Insert)

삽입 연산은 새로운 요소를 힙에 추가한 후, 힙 속성을 유지하기 위해 Heapify-Up 과정을 수행합니다.

알고리즘

새로운 요소를 힙의 마지막 위치에 추가합니다.
부모 노드와 비교하여 힙 속성이 유지되지 않는 경우, 부모와 자리를 교환합니다.
이 과정을 루트 노드까지 반복합니다.

예제 코드

void insert(MinHeap *heap, int value) {
    if (heap->size >= MAX_SIZE) {
        printf("Heap overflow\n");
        return;
    }
    int i = heap->size;
    heap->data[i] = value;
    heap->size++;

    // Heapify-Up
    while (i > 0 && heap->data[(i - 1) / 2] > heap->data[i]) {
        int temp = heap->data[i];
        heap->data[i] = heap->data[(i - 1) / 2];
        heap->data[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
}

삭제 연산 (Heap Delete)

삭제 연산은 일반적으로 루트 노드(우선순위가 가장 높은 요소)를 제거하며, 힙 속성을 유지하기 위해 Heapify-Down 과정을 수행합니다.

알고리즘

루트 노드의 값을 저장합니다.
힙의 마지막 요소를 루트 노드로 이동합니다.
자식 노드 중 우선순위가 높은 노드와 비교하여 힙 속성이 유지되지 않는 경우, 자리를 교환합니다.
이 과정을 힙의 마지막 레벨까지 반복합니다.

예제 코드

int deleteMin(MinHeap *heap) {
    if (heap->size == 0) {
        printf("Heap underflow\n");
        return -1;
    }
    int min = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;

    // Heapify-Down
    int i = 0;
    while (2 * i + 1 < heap->size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = left;

        if (right < heap->size && heap->data[right] < heap->data[left])
            smallest = right;

        if (heap->data[i] <= heap->data[smallest])
            break;

        int temp = heap->data[i];
        heap->data[i] = heap->data[smallest];
        heap->data[smallest] = temp;

        i = smallest;
    }
    return min;
}

시간 복잡도

삽입 연산: O(log n) (Heapify-Up 수행)
삭제 연산: O(log n) (Heapify-Down 수행)

특징

삽입 연산은 힙에 새로운 데이터를 추가하면서도 힙 속성을 유지합니다.
삭제 연산은 최우선순위 데이터를 제거하면서 힙 속성을 유지합니다.

삽입과 삭제 연산의 효율적인 구현은 힙 자료구조를 기반으로 우선순위 큐를 효과적으로 작동시킵니다.

힙 정렬의 개념과 구현

힙 정렬(Heap Sort)은 힙 자료구조를 활용한 효율적인 정렬 알고리즘으로, 최대 힙(Max-Heap)이나 최소 힙(Min-Heap)을 이용하여 배열을 정렬합니다. 이 알고리즘은 비교 기반 정렬 중 하나로, 시간 복잡도가 항상 O(n log n)으로 일정합니다.

힙 정렬의 원리

힙 생성(Build Heap): 주어진 데이터를 힙 구조로 변환합니다.

최대 힙을 사용하면 배열을 내림차순으로 정렬할 수 있습니다.
최소 힙을 사용하면 배열을 오름차순으로 정렬할 수 있습니다.

정렬(Sort): 힙의 루트 노드(최대값 또는 최소값)를 추출한 뒤, 힙 속성을 유지하며 데이터를 재배열합니다.

힙 정렬 알고리즘

힙 정렬은 다음 두 단계를 반복합니다:

루트 노드를 배열의 끝으로 이동합니다.
나머지 요소에 대해 힙 속성을 재구축합니다(Heapify).

힙 정렬 구현 코드

#include <stdio.h>

void heapify(int arr[], int n, int i) {
    int largest = i;        // 루트 노드
    int left = 2 * i + 1;   // 왼쪽 자식
    int right = 2 * i + 2;  // 오른쪽 자식

    // 왼쪽 자식이 루트보다 크면 갱신
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 오른쪽 자식이 현재 가장 큰 값보다 크면 갱신
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 가장 큰 값이 루트가 아니라면 교환하고 재귀 호출
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // 하위 트리를 힙화
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // 힙 생성
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 정렬
    for (int i = n - 1; i >= 0; i--) {
        // 현재 루트(최대값)를 끝으로 이동
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 남은 힙에 대해 힙화
        heapify(arr, i, 0);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    heapSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

코드 설명

heapify: 특정 노드와 그 하위 노드가 힙 속성을 만족하도록 재구성합니다.
heapSort: 배열을 힙으로 변환한 뒤, 정렬 작업을 수행합니다.
printArray: 배열 요소를 출력합니다.

시간 복잡도

힙 생성: O(n)
정렬 과정: O(n log n)
따라서 전체 시간 복잡도는 O(n log n)입니다.

힙 정렬의 장점

안정적 성능: 최악, 평균, 최상의 경우 모두 O(n log n)의 성능을 보장합니다.
제자리 정렬(In-place Sort): 추가 메모리 공간을 거의 사용하지 않습니다.

힙 정렬은 대규모 데이터 정렬 작업에 적합하며, 힙 자료구조를 효율적으로 활용하는 대표적인 알고리즘입니다.

시간 복잡도 분석

힙 자료구조와 우선순위 큐의 시간 복잡도는 주요 연산의 효율성을 이해하는 데 중요한 요소입니다. 삽입, 삭제, 힙 생성 등 각 연산의 시간 복잡도를 분석하여 힙과 힙 기반 알고리즘의 성능을 평가할 수 있습니다.

힙 연산의 시간 복잡도

삽입(Insertion)

삽입된 요소를 적절한 위치로 이동시키는 과정(Heapify-Up)이 포함됩니다.
힙의 높이는 완전 이진 트리의 특성상 O(log n)이므로 삽입 연산의 시간 복잡도는 O(log n)입니다.

삭제(Deletion)

루트 노드를 제거한 후, 마지막 요소를 루트로 이동하고 힙 속성을 유지하기 위해 Heapify-Down을 수행합니다.
이 과정의 시간 복잡도 역시 힙의 높이에 비례하므로 O(log n)입니다.

힙 생성(Build Heap)

배열을 힙으로 변환하는 과정에서 각 노드에 대해 Heapify를 수행합니다.
이 과정의 시간 복잡도는 O(n)입니다.

우선순위 큐의 시간 복잡도

우선순위 큐는 힙 자료구조를 기반으로 구현되므로 주요 연산의 시간 복잡도는 다음과 같습니다:

삽입(Enqueue): O(log n)
최우선순위 삭제(Dequeue): O(log n)
최우선순위 조회(Peek): O(1)

힙 정렬의 시간 복잡도

힙 생성(Build Heap): O(n)
정렬(Sorting): 각 요소에 대해 Heapify-Down을 수행하므로 O(n log n)

전체 시간 복잡도: O(n) + O(n log n) = O(n log n)

최악, 최선, 평균 시간 복잡도

힙의 주요 연산(삽입, 삭제, 힙 생성)은 모두 트리의 높이에 비례하므로 최악, 최선, 평균 모든 경우에 O(log n) 또는 O(n log n)의 성능을 보장합니다.

비교: 힙 기반 연산과 다른 알고리즘

힙 정렬(O(n log n))은 퀵 정렬(Quick Sort)의 최악의 경우 성능(O(n^2))보다 안정적입니다.
우선순위 큐의 삽입/삭제(O(log n))는 배열 기반 구현(O(n))보다 효율적입니다.

효율성의 의미

힙 자료구조는 삽입, 삭제, 정렬 작업에서 일관된 성능을 제공하므로 대규모 데이터 관리와 우선순위 처리가 필요한 응용에 매우 적합합니다. 특히, 힙 기반 알고리즘은 시간 복잡도의 효율성 덕분에 실시간 시스템, 네트워크 경로 탐색, 이벤트 관리 등 다양한 영역에서 활용됩니다.

예제 문제와 코드

힙과 우선순위 큐를 활용한 실제 예제를 통해 개념을 명확히 이해하고, C 언어 구현 방법을 익혀봅니다.

문제

우선순위 큐를 이용하여 작업 스케줄링 문제를 해결하세요.

작업 목록이 주어지고, 각 작업은 우선순위와 작업 이름으로 구성됩니다.
우선순위가 높은 작업을 먼저 처리해야 합니다.

코드 구현

다음은 우선순위 큐를 이용해 작업 스케줄링을 구현한 코드입니다:

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

#define MAX_SIZE 100

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

typedef struct {
    Task data[MAX_SIZE];
    int size;
} PriorityQueue;

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

// 작업 삽입
void enqueue(PriorityQueue *pq, int priority, char name[]) {
    if (pq->size >= MAX_SIZE) {
        printf("Queue overflow\n");
        return;
    }

    int i = pq->size;
    pq->data[i].priority = priority;
    strcpy(pq->data[i].name, name);
    pq->size++;

    // Heapify-Up
    while (i > 0 && pq->data[(i - 1) / 2].priority > pq->data[i].priority) {
        Task temp = pq->data[i];
        pq->data[i] = pq->data[(i - 1) / 2];
        pq->data[(i - 1) / 2] = temp;
        i = (i - 1) / 2;
    }
}

// 작업 제거
Task dequeue(PriorityQueue *pq) {
    if (pq->size == 0) {
        printf("Queue underflow\n");
        Task empty = {0, ""};
        return empty;
    }

    Task minTask = pq->data[0];
    pq->data[0] = pq->data[pq->size - 1];
    pq->size--;

    // Heapify-Down
    int i = 0;
    while (2 * i + 1 < pq->size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = left;

        if (right < pq->size && pq->data[right].priority < pq->data[left].priority)
            smallest = right;

        if (pq->data[i].priority <= pq->data[smallest].priority)
            break;

        Task temp = pq->data[i];
        pq->data[i] = pq->data[smallest];
        pq->data[smallest] = temp;

        i = smallest;
    }
    return minTask;
}

// 테스트 코드
int main() {
    PriorityQueue pq;
    initQueue(&pq);

    enqueue(&pq, 3, "Task A");
    enqueue(&pq, 1, "Task B");
    enqueue(&pq, 2, "Task C");

    printf("Processing tasks:\n");
    while (pq.size > 0) {
        Task t = dequeue(&pq);
        printf("Priority: %d, Task: %s\n", t.priority, t.name);
    }

    return 0;
}

코드 설명

enqueue: 작업을 우선순위 큐에 추가하며, 힙 속성을 유지하기 위해 Heapify-Up을 수행합니다.
dequeue: 가장 높은 우선순위를 가진 작업을 제거하며, 힙 속성을 유지하기 위해 Heapify-Down을 수행합니다.
main 함수: 작업을 추가한 후, 우선순위에 따라 작업을 처리합니다.

실행 결과

입력된 작업:

Task A (우선순위 3)
Task B (우선순위 1)
Task C (우선순위 2)

출력:

Processing tasks:
Priority: 1, Task: Task B
Priority: 2, Task: Task C
Priority: 3, Task: Task A

핵심 학습 포인트

우선순위 큐의 삽입과 삭제 연산이 어떻게 힙 속성을 유지하며 작동하는지 이해할 수 있습니다.
실용적인 문제에 힙 기반 자료구조를 적용하는 방법을 배울 수 있습니다.

요약

힙 자료구조와 우선순위 큐는 효율적인 데이터 관리와 정렬을 가능하게 하며, 다양한 응용 분야에서 활용됩니다. 본 기사에서는 C 언어를 활용해 힙의 개념과 구현, 우선순위 큐의 동작 원리와 코드를 자세히 다뤘습니다. 이러한 지식을 통해 정렬, 작업 스케줄링 등 실무 문제를 효과적으로 해결할 수 있습니다.