힙 응용 - 우선순위 큐 (Priority queue)

우선순위 큐 (Priority queue) 란?

큐는 여러개의 데이터를 넣을 수 있는 자료구조 입니다. 데이터가 넣고 뺄때는 First In First Out(FIFO) 구조를 가집니다.

우선순위 큐는 이러한 큐의 한종류로써 최대 우선순위 큐와 최소 우선순위 큐로 나뉩니다.

최대 우선순위 큐

최대 우선순위 큐는 다음의 두가지 연산을 지원하는 자료구조 입니다. (최소 우선순위 큐는 EXTRACT-MAX 대신 EXTRACT-MIN을 지원하는 자료구조입니다.)

1. INSERT(x) : 새로운 원소 x를 삽입
2. EXTRACT_MAX() : 최대값을 삭제하고 반환

MAX HEAP을 이용해서 최대 우선순위 큐를 구현할 수 있습니다.

INSERT

위의 그림은 MAX HEAP의 형태로 저장되어 있는 우선순위 큐 입니다. 현재 heap은

1. complete binary tree
2. max heap property
   조건을 만족하기 때문에 이를 유지하면서 INSERT 연산을 하기 위해서는 고려할 사항들이 있습니다.

INSERT는 새로운 노드를 추가해야하는데 complete binary tree 를 만족하기 위해서는 가장 마지막 레벨의 leaf에 추가 될 수 밖에 없습니다. 그리고 새로운 노드가 추가된 후 max heap property를 만족하기 위해서는 max-heapify 연산이 필요합니다.
INSERT의 의사 코드는 다음과 같습니다.

MAX-HEAP-INSERT(A, key){
    heap_size = heap_size + 1;
    A[heap_size] = key;
    i = heap_size;
    while(i > 1 and A[PARENT(i)] < A[i]){
        exchange A[i] and A[PARENT(i)];
        i = PARENT(i);
    }
}

위의 코드에서 A는 heap의 사이즈를 1증가 시키고, 그 자리에 새로운 key값을 넣습니다. i는 새로 추가된 노드의 인덱스입니다.
그 후 while 문에서 i > 1 (root 노드가 아니라는 의미) 이며, A[PARENT(i)] < A[i] (부모 노드에 저장된 값보다 크다는 의미) 라면 부모 노드와 값을 교환합니다.

즉, 루트 노드가 될 때까지 혹은 자신의 부모 노드보다 작을 때 까지 계속해서 교환연산을 진행합니다. 따라서 시간 복잡도는 트리의 높이에 비례하게 되고, heap은 complete binary tree이므로 O(nlogn)입니다.

EXTRACT_MAX

위의 그림은 EXTRACT_MAX 과정을 나타내고 있습니다. heap은 complete binary tree 성질을 유지하기 위해서 아무 노드나 삭제하는 것이 아니라 마지막 노드를 삭제하게 됩니다. 이때 루트 노드와 마지막 노드의 자리를 변경해 마지막 노드를 삭제 후 max-heapify를 통해 다시 max heap property를 만족하도록 만들 수 있습니다.
HEAP-EXTRACT-MAX의 의사 코드는 다음과 같습니다.

HEAP-EXTRACT-MAX(A){
    if heap-size[A] < 1
        then error "heap underflow"
    max <- A[1]
    A[1] <- A[heap-size[A]]
    heap-size[A] <- heap-size[A] - 1
    MAX-HEAPIFY(A, 1)
    return max
}

C++로 구현하기

void max_heap_insert(int a[], int size, int key) {
    int i, tmp;

    size = size + 1;
    a[size] = key;

    i = size;
    while (i > 1 && a[i / 2] < a[i]) {
        tmp = a[i / 2];
        a[i / 2] = a[i];
        a[i] = tmp;
        i = i / 2;
    }
}

int heap_extract_max(int a[], int size) {
    if (size < 1) {
        cout << "heap underflow\n";
        return -1;
    }

    int max = a[1];
    a[1] = a[size];
    max_heapify(a, size-1, 1);
    return max;
}

출처 : 2015 봄학기 알고리즘 - 부경대 권오흠 교수님