[C언어 우선순위 큐 알고리즘] 우선순위 큐 구현하기

💡 이번에는 우선순위 큐를 구현 하는 법을 배워보았다.

문제

💡 우선순위 큐 방식으로 큐를 만드시오.

당연히 없는 문제기에 대충 내가 만들었다.

해답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX_SIZE 10000

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

typedef struct priorityQueue {
    int heap[MAX_SIZE];
    int count;
} priorityQueue;

void push(priorityQueue *pq, int data) {
    if (pq->count >= MAX_SIZE) {
        return ;
    }
    pq->heap[pq->count] = data;
    int now = pq->count;
    int parent = (pq->count - 1) / 2;

    while (now > 0 && pq->heap[now] > pq->heap[parent]) {
        swap(&pq->heap[now], &pq->heap[parent]);
        now = parent;
        parent = (parent - 1) / 2;
    }
    pq->count++;
}

int pop(priorityQueue *pq) {
    if (pq->count <= 0) {
        return -9999;
    }
    int res = pq->heap[0];
    pq->count--;
    pq->heap[0] = pq->heap[pq->count];
    int now = 0;
    int leftChild = 1;
    int rightChild = 2;
    int target = now;

    while (leftChild < pq->count) {
        if (pq->heap[target] < pq->heap[leftChild]) {
            target = leftChild;
        }
        if (pq->heap[target] < pq->heap[rightChild] && rightChild < pq->count) {
            target = rightChild;
        }
        if (target == now) {
            break;
        }
        else {
            swap(&pq->heap[now], &pq->heap[target]);
            now = target;
            leftChild = now * 2 + 1;
            rightChild = now * 2 + 2;
        }
    }
    return res;
}

int main(void) {
    int n, data;
    scanf("%d", &n);
    priorityQueue pq;
    pq.count = 0;
    for (int i = 0 ; i < n ; i++) {
        scanf("%d", &data);
        push(&pq, data);
    }
    for (int i = 0 ; i < n ; i++) {
        int data = pop(&pq);
        printf("%d ", data);
    }

    return 0;
}

설명

우선순위 큐란?

• ‘우선순위’를 가진 데이터들을 저장하는 큐를 의미한다.
• 데이터를 꺼낼 때 우선 순위가 높은 데이터가 먼저 나온다는 특징이 있다.
• 일반적인 큐는 선형적인 형태를 가지고 있으나 큐는 트리(Tree) 구조로 보는 것이 합리적이다.
  • 일반적으로 우선순위 큐는 최대 힙을 이용해 구현한다.
• 우선순위 큐의 삽입과 삭제로 항상 부모 노드가 자식 노드보다 값이 크게 한다. (상향식, 하향식)

최대 힙이란?

• 최대 힙은 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리를 의미한다.

우선순위 큐 지정

typedef struct priorityQueue {
    int heap[MAX_SIZE];
    int count;
} priorityQueue;

최대 힙을 구성하기 위해 int heap[MAX_SIZE] 로 초기화해준다.

push 함수

void push(priorityQueue *pq, int data) {
    if (pq->count >= MAX_SIZE) { // pq의 count가 MAX_SIZE와 같거나 많으면 push 하지 않는다.
        return ;
    }

    pq->heap[pq->count] = data; // 항상 완전 이진트리의 마지막 원소로 들어가게 된다.
    int now = pq->count;    // now = 삽입된 위 데이터에 대한 인덱스
    int parent = (pq->count - 1) / 2;   // now에 1을 빼고 2로 나눈 값

    // 새 원소를 삽입한 이후에 상향식으로 힙을 구성한다.
    // 자신의 위치가 부모보다 크다면 스왑으로 바꿔준다.
    while (now > 0 && pq->heap[now] > pq->heap[parent]) {
        swap(&pq->heap[now], &pq->heap[parent]);
        now = parent;
        parent = (parent - 1) / 2;
    }
    pq->count++;

• pq->heap[now] > pq->heap[parent]
  • 위 int now = pq->count; 와 int parent = (pq->count - 1) / 2; 에서 구한 now 와 parent의 heap을 확인하여 이번에 들어온 데이터가 더 크다면 크지 않을 때 까지 swap하여 위치를 바꿔준다.

pop 함수

int pop(priorityQueue *pq) {
    if (pq->count <= 0) {  // 더이상 추출할 원소가 없다면 return -9999 해준다.
        return -9999;
    }
    int res = pq->heap[0];  // 추출할 원소, 즉 루트 노드
    pq->count--;
    pq->heap[0] = pq->heap[pq->count];  // 해당 루트노드에 가장 마지막 원소를 넣음
    int now = 0;
    int leftChild = 1;
    int rightChild = 2;
    int target = now;   // 자기 자신

    // 새 원소를 추출한 이후에 하향식으로 힙을 구성한다. 원소가 존재할 때만 반복한다.
    while (leftChild < pq->count) {
				// 타겟 원소가 leftChild보다 작다면 target을 leftChild로 바꿔준다.
        if (pq->heap[target] < pq->heap[leftChild]) {
            target = leftChild;
        }
				// leftChild가 rightChild보다 작다면 target을 rightChild로 바꿔준다.
				// index를 벗어나지 않게 하기 위해서 rightChild가 현재 원소의 개수보다 작을 때까지만 검사할 수 있게 한다.
        if (pq->heap[target] < pq->heap[rightChild] && rightChild < pq->count) {
            target = rightChild;
        }
        // 더 이상 내려가지 않아도 될 떄 종료
        if (target == now) {
            break;
        }
        else {
            swap(&pq->heap[now], &pq->heap[target]);
            now = target;
            leftChild = now * 2 + 1;
            rightChild = now * 2 + 2;
        }
    }
    return res;
}

• int res = pq->heap[0]; 에서 루트 노드를 추출하는 이유는 우선순위 큐이기 때문에 우선순위가 큰 원소부터 추출하기 때문이다.
• pop 함수가 push 함수보다 더 복잡한 느낌이다. 주석을 잘 읽어보자.

main 함수

int main(void) {
    int n, data;
    scanf("%d", &n);
    priorityQueue pq;
    pq.count = 0;
    for (int i = 0 ; i < n ; i++) {
        scanf("%d", &data);
        push(&pq, data);
    }
    for (int i = 0 ; i < n ; i++) {
        int data = pop(&pq);
        printf("%d ", data);
    }

    return 0;
}

main 함수는 별 거 없다.

받을 원소 개수를 정하고, count를 초기화 한 뒤 우선순위 큐에 push 해주고, 다시 pop 해주는 간단한 코드이다.

---

마치며..

이진트리도 백프로 이해를 하지 못하였는데 우선순위 큐를 백프로 이해하는 것은 쉽지 않을 것이라고 생각한다.

왜이리 어려움 투성이인지…