13. 우선순위 큐 - 필요성 / 큐와의 차이점 / 최대 힙(Max Heap) / 우선순위 큐의 삽입 / 우선순위 큐의 삭제 / 우선순위 큐의 정의 / 우선순위 큐 구현하기

우선순위 큐의 필요성

 우선순위 큐는 '우선 순위'를 가진 데이터들을 저장하는 큐를 의미한다. 데이터를 꺼낼 때 우선 순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 많이 활용되고 있다. 우선순위 큐는 운영체제의 작업 스케줄링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다.

 

우선순위 큐와 큐의 차이점

일반적인 형태의 큐는 선형적인 형태를 가지고 있지만, 우선순위 큐는 트리(Tree) 구조로 보는 것이 합리적이다. 일반적으로 우선순위 큐는 최대 힙을 이용해 구현한다. (+우선순위 큐는 '완전 이진 트리'를 이용해서 구현한다.)

 

최대 힙(Max Heap)

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

최대힙을 유지하는 트리의 예시

최대 힙의 루트 노드는 전체 트리에서 가장 큰 값을 가진다는 특징이 있다. 

항상 전체 트리가 최대 힙 구조를 유지하도록 자료구조를 만들 수 있는데, 최대 힙 구조도 큐를 기반으로 동작하기 때문에 일반적으로 push(데이터 삽입) / pop(데이터 추출) 함수로 구성된다. 

 

우선순위 큐의 삽입

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

삽입 이후, 루트 노드까지 거슬러 올라가면서 최대 힙을 구성한다.[상향식]

 

 

우선순위 큐의 삭제

삭제할 때는 루트 노드를 삭제하고, 가장 마지막(Index 상으로)원소를 루트 노드의 위치로 옮긴다.

삭제 이후엔 리프 노드까지 내려가면서 최대 힙을 구성한다. [하향식]

우선순위 큐의 정의

#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;
} //데이터 삽입 및 삭제 후 최대 힙 구성 유지를 위해 2개 데이터의 위치를 바꾸는 함수 필요

typedef struct {
    int heap[MAX_SIZE]; // 1개의 힙을 배열 형태로 만듬
    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++; //원소가 1개 늘음
}

부모 인덱스 계산하는 법(도식) = (자식인덱스 - 1) /2

 

우선순위 큐의 추출

일반적인 큐의 pop함수와는 조금 다르게 동작한다.

int pop(priorityQueue *pq){
    if(pq->count <= 0) return -9999; //더 이상 추출할 원소가 없는 경우, 리턴 값으로 문제가 있음을 알림
    int res = pq->heap[0]; //res에 추출할 원소(root 노드의 값)를 담음
    pq->count--;
    pq->heap[0] = pq->heap[pq->count]; //가장 마지막 원소를 root노드 자리에 넣기
    int now = 0, leftChild =1, rightChild = 2;
    int target = now; //target은 자기 자신을 가리킴 -> 후엔 바꾸고자하는 자식노드를 가리킴
    //새 원소를 추출한 이후, 하향식으로 힙을 구성
    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; //추출할 원소(이전 root 노드 값) 리턴
}

 

우선순위 큐의 사용

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);
    }
    system("pause");
    return 0;
}

 

요약

1. 우선순위 큐는 완전 이진 트리 형태의 힙을 이용해 구현할 수 있다.
2. 우선순위 큐의 삽입과 삭제는 O(logN)의 시간 복잡도를 가진다.
3. 따라서 우선순위 큐를 이용한 정렬은 O(NlogN)의 시간 복잡도를 가진다.

+ 우선순위 큐를 이용한 정렬을 힙정렬 이라고도 한다.