[CDS] chapter 9 : 우선순위 큐

1. 개념

이전에 정리한 자료구조 큐는 선입선출 원칙에 의해 먼저 들어온 데이터가 먼저 나가게 된다. 이는 먼저 들어온 데이터가 높은 우선순위를 갖는 것이다. 어떤 우선순위가 존재하고 데이터가 출력되는 순서가 이 우선순위에 의하는 자료구조를 자연스럽게 생각해 볼 수 있다. 이처럼 각 요소에 우선순위가 부여되어, 이중 가장 높은 우선순위의 요소가 먼저 나가는 자료구조를 우선순위 큐라고 한다. 잘 생각해보면 큐나 스택 모두 우선순위 큐의 특수한 태양으로 이해할 수 있다. 적절한 우선순위를 부여하면 우선순위 큐는 큐나 스택과 같이 동작할 것이다. 

 

구현 파트에 서술해놓은 우선순위 큐의 추상자료형을 보면 알 수 있듯이 우선순위 큐에도 당연히 여러 연산이 존재한다. 다만 이들 중에서 가장 중요한 두 연산은 삽입 연산과 삭제 연산이라고 할 수 있는데, 요소의 우선순위와 직접 관계된 연산이기 떄문이다.

2. 기본적인 구현 방법

(1) 배열을 사용하는 방법

정렬조차 되어 있지 않은 배열을 활용해서 우선순위 큐를 구현할 수 있을 것이다. 이 경우 삽입 연산은 단순히 배열의 맨 뒤에 요소를 추가하면 되기 때문에 O(1)의 시간복잡도를 갖지만, 삭제시에는 가장 높은 우선순위를 찾기 위해 모든 요소를 스캔해야 하므로 O(n)의 시간복잡도를 갖게 된다.

 

만약 배열이 우선순위에 따라 정렬된 상태라면 삭제 연산은 O(1)의 시간복잡도를 갖게된다. 그러나 이 경우에는 삽입 연산을 수행하려면 적절한 삽입 위치를 찾고 삽입 위치 뒤의 요소들을 한칸씩 이동시킨 뒤 이 자리에 삽입하게 되므로 O(n)의 시간복잡도를 갖는다.

(2) 연결 리스트를 사용하는 방법

연결 리스트를 사용한 구현 또한 배열과 마찬가지이다. 다만 높은 우선순위를 갖는 요소를 앞에 위치시키는게 유리하다. 이 경우 삭제 연산은 O(1)의 시간복잡도를 갖는다. 다만 삽입 연산의 경우 삽입위치까지 이동해야 하기 때문에 O(n)의 시간복잡도를 갖는다.

3. 힙을 활용한 구현 방법

(1) 자료구조 힙

힙(heap)이란 완전 이진트리의 일종으로 우선순위 큐를 위해 특별히 만들어진 자료구조라고 한다. 힙은 여러 개의 값들 중 가장 큰 값 또는 가장 작은 값을 빠르게 찾기 위한 자료구조이다.

 

힙의 핵심은 느슨한 정렬 상태를 유지한다는 점이다. 여기서 '느슨한 정렬 상태'란, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 상태(최대 힙의 경우이고, 최소 힙은 항상 작아야 한다)를 말한다. BST에서와 달리 왼쪽 노드의 키값이 오른쪽 노드의 키값보다 작아야 한다거나, 중복된 키값이 허용되지 않는다거나 하는 제한은 존재하지 않는다.

(2) 힙의 구현

힙은 완전 이진트리이기 때문에 1차원 배열로 구현할 수 있다. 첫 인덱스(0)은 비우고, 위에서부터 내려가면서 차례대로 번호를 붙이면 다음과 같은 수식이 성립하게 된다.

• 왼쪽 자식의 인덱스 = 부모 인덱스 * 2
• 오른쪽 자식의 인덱스 = 부모 인덱스 * 2 + 1
• 부모의 인덱스 = 자식의 인덱스 / 2

트리처럼 힙도 연결 리스트로 구현할 수는 있지만, 일반적으로는 1차원 배열로 구현하는 것이 훨씬 효율적이다.그 이유는 힙이 완전 이진 트리 구조이기 때문에, 새로운 노드는 항상 트리의 가장 마지막 위치에 추가되어야 하기 때문이다. 배열을 사용할 경우 이 마지막 위치를 인덱스로 쉽게 계산할 수 있지만, 연결 리스트로 구현하면 해당 위치를 찾기 위해 트리를 탐색해야 하므로 비효율적이다.

 

상세한 구현은 아래에서 하되, 교재에서 소개하는 삽입 연산과 삭제 연산의 구현 과정의 컨셉만 짚고 넘어가자. 우선 삽입 연산은 '신입사원을 말단자리에 앉힌 다음 능력에 따라 승진시키는 것'과 유사하다고 한다. 반대로, 삭제 연산은 '사장 자리가 비게 되면 제일 말단 사원을 사장자리로 올린 뒤 강등시키는 것'과 유사하다고 한다. 직관적으로 머리에 꽂히는 좋은 설명이다!

3. 우선순위 큐 구현

(1) 우선순위 큐 ADT

insert(pq, item) ::= 우선순위에 따라 item을 우선순위 큐 pq에 삽입
delete(pq) ::= 우선순위가 가장 높은 항목을 우선순위 큐 pq에서 제거하고 반환
peek(pq) ::= 우선순위가 가장 높은 항목을 제거하지 않고 반환
is_empty(pq) ::= 우선순위 큐 pq가 비어 있는지 확인
is_full(pq) ::= 우선순위 큐 pq가 가득 찼는지 확인
clear(pq) ::= 우선순위 큐 pq의 모든 항목을 제거
print_queue(pq) ::= 우선순위 순서대로 우선순위 큐 pq의 모든 요소를 출력

(2) 구현 : 업무 매니저 시뮬레이션

적절한 과제가 없어 GPT를 통해 우선순위 큐를 활용할 수 있는 '업무 매니저 시뮬레이션' 프로그래밍 과제를 생성하였다. 동작 모습은 다음과 같다.

 

main.c, simulate.c, priority_queue.c 는 각각 다음과 같다.

main.c

#include <Windows.h>
#include <stdio.h>
#include <stdbool.h>
#include "./include/priority_queue.h"
#include "./include/simulate.h"

int main() {

    SetConsoleOutputCP(CP_UTF8);

    Queue task_queue;
    task_queue.nTask = 0;

    while (true) {

        printf("[ MENU ] 1: generate, 2: display, 3: current, 4: complete, 5: add, 6: quit\n");
        printf("Please enter a command:");
        
        int command;
        
        if (scanf("%d", &command) != 1) {
            printf("wrong input!!!\n");
            while (getchar() != '\n');
            continue;
        }

        switch (command) {
            case 1:
                task_queue = generate_task();
                break;
            case 2:
                display_all(task_queue);
                break;
            case 3:
                display_current(task_queue);
                break;
            case 4:
                task_queue = complete_task(task_queue);
                break;
            case 5:
                task_queue = add_task(task_queue);
                break;
            case 6:
                printf("👋 Program terminated.\n");
                return 0;
            default:
                printf("wrong input!!!\n");
                break;
        }
    } 
}

 

simulate.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include "./priority_queue.h"
#include "./simulate.h"

Queue create_queue() {
    Queue task_queue;
    task_queue.nTask = 0;
    return task_queue;
}

Queue generate_task() {
    
    Queue task_queue = create_queue();
    
    int genTask;
    while (true) {
        printf("Enter number of tasks to generate: ");
        scanf("%d", &genTask);
        // 정수가 아닌 경우의 예외처리 필요
        if (genTask <= MAX_TASKS) break;
        else printf("There are currently %d remaining task positions.\n", MAX_TASKS);
    }

    srand(time(NULL));
    for (int i = 0; i < genTask; i++) {
        Node data;
        data.priority = rand() % 10 + 1;
        sprintf(data.name, "Task%d", i);
        task_queue = insert(task_queue, data);
        printf("✅ %s (Priority: %d) added.\n", data.name, data.priority);
    }

    return task_queue;
}

void display_all(Queue task_queue) {
    if (task_queue.nTask == 0) {
        printf("⚠️  The queue is empty.\n");
    }
    else {
        printf("📋 Current Task Queue: \n");
        print_queue(task_queue);
    }
}

void display_current(Queue task_queue) {
    if (task_queue.nTask == 0) {
        printf("⚠️  The queue is empty.\n");
    }
    else {
        printf("🔥 Current Task: ");
        Node current = peek(task_queue);
        print_node(current);
    }
}

Queue complete_task(Queue task_queue) {
    if (task_queue.nTask == 0) {
        printf("⚠️  The queue is empty.\n");
        return task_queue;
    }
    else {
        Queue after_queue;
        after_queue = remove_task(task_queue);
        printf("✅ %s completed.\n", peek(task_queue).name);
        return after_queue;
    }
}

Queue add_task(Queue task_queue) {
    Node data;
    printf("Enter task name:");
    scanf("%s", data.name);
    printf("Enter priority (1~10):");
    scanf("%d", &data.priority); // 마찬가지로 예외처리 필요
    
    task_queue = insert(task_queue, data);
    printf("✅ %s (Priority: %d) added.\n", data.name, data.priority);
    return task_queue;
}

 

priority_queue.c

#include <stdio.h>
#include <stdbool.h>
#include "./priority_queue.h"


Queue heapifyup(Queue queue, int index) {
    int parent_idx = index / 2;
    while (parent_idx >= 1) {
        Node parent = queue.tasks[parent_idx];
        Node child = queue.tasks[index];
        if (parent.priority < child.priority) {
            queue.tasks[parent_idx] = child;
            queue.tasks[index] = parent;
            index /= 2;
            parent_idx /= 2;
        }
        else break;
    }
    return queue;
}

Queue heapifydown(Queue queue, int index) {
    while (index * 2 <= queue.nTask) {
        Node parent = queue.tasks[index];
        int left = index * 2;
        int right = index * 2 + 1;
        int target = left;

        if (right <= queue.nTask && queue.tasks[right].priority > queue.tasks[left].priority) {
            target = right;
        }

        Node child = queue.tasks[target];
        if (parent.priority < child.priority) {
            queue.tasks[target] = parent;
            queue.tasks[index] = child;
            index = index * 2;
        }
        else break;
    }

    return queue;
}

Queue insert(Queue queue, Node item) {
    if (queue.nTask == MAX_TASKS) {
        printf("The task queue is full!!\n");
    }
    else {
        queue.nTask += 1;
        int curr = queue.nTask;
        queue.tasks[curr] = item;

        queue = heapifyup(queue, curr);
    }
    return queue;
}

Queue remove_task(Queue queue) {
    queue.tasks[1] = queue.tasks[queue.nTask];
    queue.nTask -= 1;
    int curr = 1;

    queue = heapifydown(queue, curr);

    return queue;
}

Node peek(Queue queue) {
    return queue.tasks[1];
}

void print_node(Node node) {
    printf("%s (Priority: %d)\n", node.name, node.priority);
}

void print_queue(Queue queue) {
    while (!is_empty(queue)) {
        print_node(peek(queue));
        queue = remove_task(queue);
    }
}

int is_empty(Queue queue) {
    return queue.nTask == 0;
}

(3) 구현 후기

• 우선순위 큐는 완전 이진트리로 구현되기 때문에 첫 인덱스를 1부터 시작하면 부모 = 자식 / 2, 왼쪽 자식 = 부모 * 2, 오른쪽 자식 = 부모 * 2 + 1의 관계가 성립한다.
• 우선순위 큐 구현에서는 새로운 요소를 삽입하거나 삭제할때의 방식을 기억하는 것이 중요하다. 새로운 요소 삽입 시 가장 말단에서 시작하여 맞는 위치까지 승진시키는 방식으로 진행되고, 삭제시 루트 노드 자리에 말단 노드를 위치시킨 뒤 맞는 위치까지 하향시키는 방식으로 진행됨을 기억하자.
• 여담으로 자료구조 구현 중에서 우선순위 큐 구현이 가장 재밌었다.