우선순위 큐 (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의 의사 코드는 다음과 같습니다.

1
2
3
4
5
6
7
8
9

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의 의사 코드는 다음과 같습니다.

1
2
3
4
5
6
7
8
9

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++로 구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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 봄학기 알고리즘 - 부경대 권오흠 교수님

저번 포스팅에서는 힙(Heap)과 max-heapify에 대해 알아보았습니다. 이번 포스팅에서는 직접 1차원 배열을 heap 구조로 변경한 후 힙 정렬을 해보겠습니다.

1차원 배열을 힙(Heap) 으로 만들기

먼저 의사 코드는 다음과 같습니다.

1
2
3
4

BUILD-MAX-HEAP
    heap-size[A]<-length[A]
    for i <- |length[A]/2| downto 1
        do MAX-HEAPIFY(A,i)

i가 A 배열의 길이 / 2 부터 시작하는 이유는 리프 노드에서는 max-heapify 과정이 필요 없기 때문입니다.

힙을 만드는데의 시간 복잡도는 다음과 같습니다.
MAX-HEAPIFY 연산의 시간 복잡도는 log(n) 입니다. 그런데 for 문이 n/2 돌기 때문에 n/2*log(n)이며 빅 오로 표기하면 O(n*log(n))이 됩니다.
이는 루트 노드만 고려하여 상당히 러프하게 계산한 것이기 때문에, 정확하게 계산한다면 시간 복잡도는 **O(n)**이 됩니다.

힙 정렬(Heap sort) 하기

힙 정렬은 다음과 같은 순서로 실행됩니다.

1. 주어진 데이터를 힙으로 만든다
2. 힙에서 최대값(루트 노드)을 가장 마지막 값과 바꾼다.
3. 힙의 크기가 1 줄어든 것으로 간주한다. 즉, 마지막 값은 힙의 일부가 아닌것으로 간주한다.
4. 루트 노드에 대해서 HEAPIFY(1)한다.
5. 2~4번을 반복한다.

데이터를 힙으로 만들면 인덱스 1의 값이 가장 최대값 이므로 마지막 값과 바꿉니다.
그리고 마지막값은 정렬된 값으로 간주하고 더 이상 신경쓰지 않아도 됩니다.
그렇게 줄여나간다면 결국 정렬된 상태의 배열이 완성됩니다.

힙 정렬의 의사 코드는 다음과 같습니다.

1
2
3
4
5
6

HEAPSORT(A)
    BUILD-MAX-HEAP(A)             // O(n)
    for i <-heap-size downto 2 do // n-1 times
        exchange A[1] <-> A[i]    // O(1)
        heap_size <- heap_size -1 // O(1)
        MAX-HEAPIFY(A,1)          // O(log(n))

총 시간 복잡도는 **nlogn**이 됩니다.

C++로 힙 정렬 구현하기

다음과 같이 C++로 힙 정렬을 구현할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#include <iostream>
#include <stdlib.h>

#define ITEM_SIZE 10

using namespace std;

void print_arr(int a[], int size) {
    for (int i = 0; i < size; i++) {
        cout << a[i] << ' ';
    }
    cout << '\n';
}

void max_heapify(int a[], int size, int idx) {
    int left = idx * 2;
    int right = (idx * 2) + 1;
    int largest = idx;
    int tmp = 0;

    // 왼쪽 자식 노드와 비교
    if (left < size && a[left] > a[largest]) {
        largest = left;
    }

    // 오른쪽 자식 노드와 비교
    if (right < size && a[right] > a[largest]) {
        largest = right;
    }

    // 부모 노드보다 자식 노드가 큰 경우 교환
    if (largest != idx) {
        tmp = a[largest];
        a[largest] = a[idx];
        a[idx] = tmp;
        // 재귀 호출
        max_heapify(a, size, largest);
    }
}

void build_max_heap(int a[], int size) {
    for (int i = size / 2; i > 0; i--) {
        max_heapify(a, size, i);
    }
}

void heap_sort(int a[], int size) {
    int tmp = 0;

    build_max_heap(a, size);
    for (int count = size - 1; count > 0; count--) {
        // 루트 노드를 가장 마지막 노드와 교환
        tmp = a[count];
        a[count] = a[1];
        a[1] = tmp;
        // 힙 구조 유지
        max_heapify(a, count, 1);
    }
}

int main() {
    int a[ITEM_SIZE] = { 0, }; // 루트 노드는 1번 인덱스 부터 시작
    for (int i = 1; i < ITEM_SIZE; i++) {
        a[i] = (rand() % (ITEM_SIZE * 10)) + 1;
    }

    print_arr(a, ITEM_SIZE);
    heap_sort(a, ITEM_SIZE);
    print_arr(a, ITEM_SIZE);
    return 0;
}

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

힙 정렬은 힙, 바이너리 힙, 이진 힙이라고 부르는 자료구조를 이용하는 정렬 알고리즘입니다.

힙 정렬의 특징은 다음과 같습니다.
1.최악의 경우에도 시간 복잡도가 nlogn이 되는 빠른 정렬이다.
2.힙 정렬은 알고리즘을 구현하는데 추가적인 배열이 필요하지 않다.
3.이진 힙(바이너리 힙) 자료구조를 사용한다.

먼저 힙 정렬을 구현하기 전에, 힙 이라는 자료구조에 대해 알아보겠습니다.

힙(Heap) 이란?

힙(Heap)은

1. complete binary tree(완전 이진 트리) 이면서
2. heap property를 만족해야 합니다.

위의 그림에서는 **full binary tree(포화 이진 트리)**와 **complete binary tree(완전 이진 트리)**에 대해 설명하고 있습니다.

binary tree(이진 트리)란 한 노드가 최대 2개의 자식 노드를 가지는 트리 입니다. 따라서, 위의 2개 트리는 모두 이진 트리입니다. 이진 트리는 이진 탐색 트리(BST)와 이진 힙(Binary Heap)의 구현에 흔히 사용됩니다.

full binary tree(포화 이진 트리)란 이진 트리중에 모든 레벨의 노드 들이 꽉 차있는 형태를 말합니다.

complete binary tee(완전 이진 트리)는 마지막 레벨을 제외하면 완전히 꽉 차있고, 마지막 레벨에는 가장 오른쪽 부터 연속된 몇개의 노드가 비어있을 수 있는 트리를 말합니다. 따라서 포화 이진 트리는 완전 이진 트리이기도 합니다.

위의 2번째 조건에서 heap property를 만족해야 한다고 했습니다. 이 heap property는 2개의 조건으로 나누어집니다.

1. max heap property - 부모 노드는 자식 노드보다 데이터가 크거나 같다.
2. min heap property - 부모 노드는 자식 노드보다 데이터가 크거나 작다.

max와 min 모두 대칭적 관계이므로 모든 알고리즘에 적용되나 상황에 따라서 간단하게 사용할 수 있는 것을 씁니다. 여기서는 max-heap property를 다루겠습니다.

(a)의 3개 트리는 모두 heap 입니다. (완전 이진 트리이면서 heap property를 만족합니다.)
(b)의 3개 트리는 heap이 아닙니다. (완전 이진 트리이지만, (max)heap property를 만족하지 않습니다.)
(c)의 2개 트리도 heap이 아닙니다. (완전 이진 트리를 만족하지 않습니다.)

위의 (a), (b), (c)는 모두 다 heap입니다.
(a), (b), (c)는 동일한 데이터를 갖고 있는 서로 다른 heap입니다. 즉, 여러가지 모양의 heap이 존재할 수 있는 것입니다.

Heap은 1차원 배열을 사용해 표현할 수 있습니다. 같은 레벨에서 왼쪽부터 배열로 저장하면 1차원 배열이 됩니다. 일반적인 트리에서는 부모 자식간의 관계를 식을 통해 표현할 수 없지만 Heap은 complete binary tree이므로 배열의 인덱스만으로 부모와 자식의 관계를 표현할 수 있습니다. 루트 노드가 배열의 1번 인덱스부터 시작한다면 다음과 같은 표현식을 사용할 수 있습니다.

• 루트 노드 : A[1]
• A[i]의 부모 노드 : A[i/2]
• A[i]의 왼쪽 자식 노드 : A[2i]
• A[i]의 오른쪽 자식 노드 : A[2i+1]

따라서 Heap은 1차원 배열을 통해 표현이 가능하기 때문에 불필요하게 트리 자료구조를 따로 만들어 사용해 구현할 필요가 없습니다.

Max-heapify 란?

지금부터는 어떤 1차원 배열의 데이터가 있을 때 이 1차원 배열을 Heap으로 변환하는 과정에 대해 알아보겠습니다. (이번 포스팅에서는 max heap만을 다루기로 했으므로 max heap을 만드는 방법에 대해 알아보겠습니다.)
일반 1차원 배열은 max-heapify라는 연산 과정을 통해 max heap으로 만들수 있습니다.

max-heapify 연산을 하기 위한 전제조건을 위의 그림에서 보여주고 있습니다.

1. 트리의 전체 모양은 complete binary tree이다.
2. 왼쪽 서브 트리(subtree)는 그 자체로 heap이다.
3. 오른쪽 서브 트리(subtree)는 그 자체로 heap이다.

여기서 유일하게 루트 노드만이 heap property를 만족하지 않을때, max-heapify 연산을 통해 heap property를 만족하게 만들 수 있습니다.

위의 그림에서 루트 노드는 자신의 자식 노드중에 더 큰값과 자리를 교체 합니다. 그 후 교체된 노드에서 다시 max-heapify 연산을 통해 max-heap property를 만족할 때까지 반복합니다.

결국 max-heapify는 동일한 과정을 반복하고 있기 때문에 **recursion(재귀)**로 구현이 가능합니다.

1
2
3
4
5
6
7
8
9

MAX-HEAPIFY(A, i){
    if there is no child of A[i]
        return;
    k <- index of the biggest child of i;
    if A[i]>=A[k]
        return;
    exchange A[i] and A[k];
    MAX-HEAPIFY(A, k);
}

첫번째 조건은 base case로서, 자식 노드가 없다면 가장 아래의 레벨에 위치한 리프노드이기 때문에 종료합니다. 만약 자식 노드가 있다면 큰 자식 노드의 인덱스를 k로 지정합니다. 그 후 부모 노드와 값을 비교해 부모 노드가 크다면 max-heapify 과정을 종료하고, 자식 노드의 값이 크다면 부모 노드와 값을 교환한 후 다시 max-heapify를 재귀 호출 합니다.

1
2
3
4
5
6
7
8
9

MAX-HEAPIFY(A, i){
    while A[i] has a child do
        k<- index of the biggest child of i;
        if A[i]>= A[k];
            return;
        exchange A[i] and A[k];
        i=k;
    end
}

같은 함수를 iterate하게 구현한 코드입니다. 주요 함수의 동작 원리는 같습니다.

max-heapify의 시간 복잡도는 루트 노드로부터 마지막 레벨까지 비교, 교환 연산을 하므로 트리의 높이보다 많은 시간이 필요하지 않습니다. 따라서 시간 복잡도는 높이에 의해서 결정되며, O(h)입니다.
일반적인 이진트리가 아닌 complete binary tree이므로 노드의 개수를 n이라 하면, **시간 복잡도는 O(logn)**이 됩니다.

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