우선순위 큐

  • 우선순위 큐는 '우선순위'를 가진 데이터를 저장하는 큐를 의미한다. 데이터를 꺼낼 때 우선순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 많이 활용되고 있다.

  • 우선순위 큐는 운영체제의 작업 스케쥴링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다.

  • 우선순위 큐는 트리 구조로 보는 것이 합리적이다. 일반적으로 우선순위 큐는 최대 힙을 이용하여 구현한다.

image.png

최대힙 (Max Heap)

  • 최대 힙은 부모 노드가 자식노드 보다 값이 큰 완전 이진트리를 의미한다.
  • 즉, 모든 부모 노드가 자식보다 값이 커야 한다.
  • 최대힙의 root node는 항상 최대값을 가진다.
  • 전체 트리가 최대 힙 구조를 유지하도록 자료구조를 만들어야 한다.

[최대힙]
![image.png](https://images.velog.io/post-images/pa324/27f5c7f0-e711-11e9-9e4c-35b0af6c260b/image.png

[최대힙x]
부모보다 자식이 더 크기때문에 최대힙이 아니다.
image.png

[루트노드]
image.png

우선순위 큐의 삽입

먼저 아래와 같이 구성된 트리가 있다.

image.png

삽입할 원소는 완전 이진 트리를 유지하는 형태로 순차적으로 삽입된다.

image.png

삽입 이후에는 루트 노드까지 거슬러 올라가면서 최대 힙을 구성한다. (상향식)
즉, 부모노드와 비교를 해서 부모노드가 삽입한 노드의 값보다 작다면 교체한다.
(logN의 시간복잡도를 가진다.)

image.png

image.png

image.png

우선순위 큐의 삭제

삭제를 할 때는 루트노드를 삭제하고, 가장 마지막 원소를 루트 노드의 위치로 옮겨준다.

먼저, 루트노드인 9를 삭제한다.
image.png

가장 마지막 원소를 루트 노드의 위치로 옮긴다.
image.png

이제 교체된 루트노드부터 하향식으로 내려가면서 최대 힙을 구성한다.(하향식) 현재 노드보다 큰 값이 있으면 교체한다.

image.png

image.png

우선순위 큐 구현

우선순위 큐 정의

#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];
    in count;
} priorityQueue;

우선순위 큐의 삽입 && 삭제

#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;  // 부모노드에 삽입된 노드가 있으므로 now를 부모노드 값으로 한다 
        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, leftChild = 1, 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;
}

삽입시 int parent = (pq->count - 1) / 2 의 의미는 삽입된 노드의 부모노드이다.

image.png