[자료구조] 우선순위큐(Priority Queue)란?

우선순위큐란

큐는 먼저 들어오는 데이터가 먼저 나가는 FIFO 형식의 자료구조이다. 하지만 우선순위큐는 먼저 들어오는 데이터가 아니라 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

 

우선순위큐 구현방법

• 배열을 이용한 우선순위 큐
• 연결리스트를 이용한 우선순위 큐
• 힙을 이용한 우선순위 큐

배열과 연결리스트는 선형 구조의 자료구조이므로 삽입 도는 삭제 연산을 위한 시간복잡도는 O(n)이다.

반면 힙트리는 완전이진트리 구조이므로 힙트리의 높이는 log₂(n+1)  이며, 힙의 시간복잡도는 O(log₂n)이다. 이 글에서는 힙을 이용하여 우선순위 큐를 구현해보겠다. 힙에 관한 내용은 아래 글을 참고하자.

[자료구조] 힙(Heap)이란?

---

 

 

우선순위큐 ADT

• create(): 우선순위큐를 생성한다.
• init(q): 우선순위큐 q를 초기화한다.
• is_empty(): 우선순위큐 q가 비었는지 검사한다.
• is_full(): 우선순위큐 q가 가득 찼는지 검사한다.
• insert(q, x): 우선순위큐 q에 요소 x를 추가한다.
• delete(q): 우선순위큐로부터 가장 우선순위가 높은 요소를 삭제하고 반환한다.
• find(q): 우선 순위가 가장 높은 요소를 반환한다.

가장 중요한 연산은 insert연산과 delete연산이다. 우선순위큐는 최소와 최대 2가지로 이루어진다.

---

 

 

우선순위큐 힙

• 배열을 이용한 방법은 모든 이진 트리를 포화 이진 트리라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법이다.
• n의 부모 노드의 인덱스(index)는 n/2
• n의 왼쪽 자식 노드의 인덱스는 2n
• n의 오른쪽 자식 노드의 인덱스는 2n + 1

---

 

 

우선순위큐 삽입

힙에 삽입을 하기 위해서는 힙 트리의 성질을 만족시키면서 새로운 요소를 추가해야 한다.

1. 우선 완전이진트리의 마지막 노드에 이어서 새로운 노드를 추가한다.
2. 추가된 새로운 노드를 부모의 노드와 비교하여 교환한다.
3. 정상적인 힙트리가 될 때 까지 (더이상 부모노드와 교환할 필요가 없을 때까지) 2번을 반복한다.

최악의 경우 새로 추가된 노드가 루트노트까지 비교하며 올라가야 하므로 시간복잡도가 O(log₂n)이다.

---

 

 

우선순위큐 삭제

힙 트리에서 루트노드가 가장 우선순위가 높으므로 루트 노드를 삭제해야 한다.

삭제가 이뤄진 후 힙 트리의 성질이 유지돼야 하므로 아래와 같은 방법으로 삭제를 진행한다.

1. 루트 노드를 삭제한다.
2. 루트 노드가 삭제된 빈자리에 완전이진트리의 마지막 노드를 가져온다.
3. 루트 자리에 위치한 새로운 노드를 자식 노드와 비교하여 교환한다.
   이때 최대 힙인 경우 자식노드 중 더 큰 값과 교환을 하며, 최소 힙인 경우 더 작은 값과 교환을 한다.
4. 정상적인 힙트리가 될 때까지 (더 이상 자식노드와 교환할 필요가 없을 때까지) 3번을 반복한다.

삭제 연산 또한 최악의 경우 루트노트부터 가장 아래까지 내려가야 하므로 시간복잡도가 O(log₂n)이다.

---

 

 

전체 코드

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define MAX_SIZE 200
typedef struct {
    int key;
} element;

typedef struct {
    element heap[MAX_SIZE];
    int heap_size = 0;
}HeapType;

HeapType *create(){
    return(HeapType*) malloc(sizeof(HeapType));
}

void init(HeapType* h) {
    h->heap_size = 0;
}

void insert_max_heap(HeapType *h, element item){
    int i;
    i = ++(h->heap_size);
    //트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
    while((i!=1) && (item.key > h->heap[i/2].key)){
        h->heap[i] = h->heap[i/2];
        i /= 2;
    }
    h->heap[i] = item;
}

element delete_max_heap(HeapType *h){
    int parent, child;
    element item, temp;
    item = h->heap[1];
    temp = h->heap[(h->heap_size)--];
    parent = 1;
    child = 2;
    while(child <= h->heap_size){
        if((child < h->heap_size) && (h->heap[child].key) < h->heap[child + 1].key){
            child++;
        }
        if(temp.key > h->heap[child].key)
            break;
        h->heap[parent] = h->heap[child];
        child *= 2;
    }
    h->heap[parent] = temp;
    return item;
}



int main(void){
    element  e1 = {40}, e2 = { 5}, e3 = {30};
    element e4,e5,e6;
    HeapType* heap;

    heap = create();
    init(heap);

    insert_max_heap(heap, e1);
    insert_max_heap(heap, e2);
    insert_max_heap(heap, e3);

    e4 = delete_max_heap(heap);
    printf("<%d>", e4.key);
    e5 = delete_max_heap(heap);
    printf("<%d>", e5.key);
    e6 = delete_max_heap(heap);
    printf("<%d>", e6.key);

    free(heap);
    return 0;
}