일반적인 큐(Queue)는 First in-First Out 구조입니다.
즉, 어떤 부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조였습니다.
하지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것 것을 말합니다.
우선순위 큐는 힙(Heap)이라는 자료구조를 가지고 구현할 수있기 때문에 이 둘을 묶어서 같이 쓴 것입니다.
[주의] 왜 우선순위 큐는 배열이나 연결리스트로 구현하지 않을까?
(1) 만일 배열로 구현한다고 가정합니다. 우선순위가 높은 순서대로 배열의 가장 앞부분부터 넣는다면, 우선순위가 높은 데이터를 반환하는 것은 맨 앞의 인덱스를 바로 이용하면 되므로 어렵지 않습니다.
하지만 우선순위가 중간인 것이 들어가야 하는 삽입 과정에서는 뒤의 데이터까지 인덱스를 모두 한 칸씩 뒤로 밀어야 하는 단점이 있습니다.
최악의 경우 삽입해야 하는 위치를 찾기 위해 모든 인덱스를 탐색해야 합니다. 즉 이 때의 시간 복잡도는 자료가 n개라고 할 때 O(n) 이 됩니다. → 배열로 구현 시 시간 복잡도 : 삭제는 O(1), 삽입은 O(n)
(2) 만일 연결리스트로 구현한다고 가정합니다. 이 또한 우선 순위가 높은 순서대로 연결을 시키면, 우선순위가 높은 데이터의 반환은 배열과 마찬가지로 쉽습니다.
하지만 연결리스트 또한 삽입의 과정 또한 배열과 마찬가지로 그 위치를 찾아야 합니다. 최악의 경우 맨 끝에까지 가게 됩니다. → 연결리스트로 구현 시 시간 복잡도 : 삭제는 O(1), 삽입은 O(n)
(3) 우선순위 큐를 힙으로 구현한다고 가정합니다. 힙의 경우 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 계속 이루어집니다. (아래에서 다룰 것입니다)
즉, 이진 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 갯수는 2배 증가하며, 비교 연산 횟수는 1회 증가합니다. 즉 삭제나 삽입 모두 최악의 경우에는 O(log2n) 의 시간 복잡도를 가집니다. → 힙으로 구현 시 시간 복잡도 : 삭제는 O(log2n), 삽입은 O(log2n)
이처럼 배열이나 연결 리스트가 삭제에서는 시간 복잡도의 우위를 점할지라도, 삽입의 시간 복잡도가 힙 기반이 월등하기 때문에, 편차가 심한 배열과 연결리스트보다는 힙으로 구현하는 것입니다.
1. 힙(Heap)
위에서 우선순위 큐에 대해서는 간략히 설명했으니, 이를 구현하기 위한 힙에 대해 알아봅시다.
(1) 힙은 Complete Binary Tree(완전 이진 트리) 이다.
(2) 모든 노드에 저장된 값(우선순위)들은 자식 노드들의 것보다 (우선순위가) 크거나 같다.
※ 직접 연결된 자식-부모 노드 간의 크기만 비교하면 됩니다.
※ 힙으로 우선순위 큐를 구현할 때에는 노드에 저장된 값을 우선순위로 봅니다.
따라서 힙은 루트 노드에 우선순위가 높은 데이터를 위치시키는 자료구조가 됩니다.
그러므로 우선순위 큐를 구현하기에 딱 맞는 자료구조 이기도 합니다. 힙에 저장된 노드를 뺄 때마다 우선순위가 높은 데이터 먼저 빠져나오기 때문입니다.
우선순위 큐를 들어가기 전에 힙 자체에 대해서만 살펴보도록 하겠습니다.
최대 힙(Max Heap)은 완전 이진트리이면서, 루트 노드로 올라갈수록 저장된 값이 커지는 구조입니다.
그리고 우선순위는 값이 큰 순서대로 매깁니다.
최소 힙(Min Heap)은 완전 이진트리이면서, 루트 노드로 올라갈수록 값이 작아지는 구조입니다.
그리고 우선순위는 값이 작은 순서대로 매깁니다.
최대 힙이던 최소 힙이던 루트 노드에는 우선순위가 높은 것이 자리잡게 됩니다.
2. 힙(Heap)의 데이터 저장 개념
2-1. 최소 힙에 저장할 때
만일 위와 같은 최소 힙에 어떤 노드 하나가 추가로 들어오게 되는 상황을 가정합시다. 노드에 저장된 값들을 우선순위로 생각하며, 숫자가 작은 순서대로 우선순위가 높은 것입니다.
제일 먼저, 들어올 새 노드를 ‘우선순위가 가장 낮다는 가정을 하고’ ‘맨 끝 위치’에 저장합니다. 맨 끝 위치에 저장한다는 것도 완전 이진트리를 만족하는 틀 안에서 이루어져야 하므로, 위 그림에서는 새로 들어올 노드가 노드 7의 left Child 로 들어가야 합니다.
그리고 부모 노드와 우선 순위를 비교해서 위치가 바뀌어야 하면 바꿉니다. 위치가 맞을 때까지 계속 반복합니다. 새로 들어올 노드의 값이 3이라고 가정해 보겠습니다.
대략적인 과정은 이렇습니다. 최대 힙은 반대로 부모와 비교해 자식이 크면 서로 자리바꿈 하면 됩니다.
그러면 이렇게 우선순위 큐를 나타내기 적합한 완전 이진트리인 ‘힙(Heap)’은 무엇을 기반으로 구현하는 것이 용이할까요? 여기에서는 배열 구현이 좋습니다.
[주의] 힙(Heap) 은 이진 트리입니다. 그리고 ‘이진 트리를 구현하는 도구’가 배열이 될 수도, 연결리스트가 될 수도 있는 것입니다.
맨 위에서 우선순위 큐는 배열, 연결리스트가 아니라 힙으로 구현해야 가장 좋다고 했는데, 여기서는 왜 갑자기 배열이 나오나? 라고 헷갈리면 안 됩니다. 그리고 힙을 배열로 구현함으로써, 위의 상황을 코드로 구현하는 것은 생각보다 간단합니다.
(그리고 노드의 값이 곧 우선순위라, 특별한 우선순위의 조건이 없으므로 구현이 쉽기도 합니다.)
힙을 배열로 구현할 때에는, 인덱스 1부터 사용하는 것이 일반적입니다.
그것이 직관적이기도 하고, 다루기에 용이해서입니다.
최소 힙의 소스코드 구현(저장까지만)
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
include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
int heap[MAX_SIZE];
void push(int item, int *n)
{
int i = 0;
i = ++(*n);
/* 개념은 부모-자식 간 비교하면서 즉시 서로 자리를 바꾸는 것이지만 */
/* 실제 코드 구현상에서는 들어올 자식보다 작았던 부모는 먼저 그 자리로 바꾼 뒤 */
/* while문 빠져나올 때 새로 들어올 자식을 최종적으로 넣으면 됨. */
while ((i != 1) && item < heap[i/2]) {
heap[i] = heap[i / 2]; // 원래 자식 들어갈 자리에 부모의 값 저장
i = i / 2; // 새로 들어올 자식이 기존 부모자리에 들어갈 것을 대비해 i를 반 줄임
}
heap[i] = item;
}
int main(void)
{
int input;
int n = 0, count = 0;
printf("Min Heap 구현 - 숫자를 입력하세요.\n");
printf("*****숫자 입력(-1을 입력하면 입력 종료)*****\n");
while (1)
{
scanf("%d", &input);
if (input == -1)
break;
push(input, &n);
count++;
}
printf("Level Order Traversal : ");
for (int i = 1; i <= count; i++) {
printf("%d ", heap[i]);
}
}
1
2
3
4
5
6
7
8
9
10
Min Heap 구현 - 숫자를 입력하세요.
*****숫자 입력(-1을 입력하면 입력 종료)*****
1
2
3
4
5
-1
>> Level Order Traversal : 1 2 3 4 5
위의 코드에서 단 하나만 고치면 Max Heap(최대 힙)을 구현할 수 있습니다.
그리고 1부터 5까지 입력할 경우, Level order Traversal의 결과는 5 4 2 1 3 이 나오게 됩니다.
3. 힙(Heap)의 데이터 삭제 개념
3-1. 최소 힙에서 삭제할 때
우선순위 큐의 구현을 위해 사용하기로 하였습니다.
우선순위 큐에서의 pop은 곧, 가장 우선순위가 높은 데이터를 빼낸다는 의미입니다.
우선순위 큐의 pop을 힙에 대입해 본다면, 힙의 루트 노드를 반환(삭제) 하는 것과 같을 것입니다.
힙에서 가장 우선순위가 높은 데이터는 루트노드인데, 이 루트 노드를 삭제하면서 힙의 구조를 그대로 유지하는 것이 관건입니다. (이 힙의 구조를 유지하는 과정을 heapify라고 합니다.)
삭제의 개념은 아래와 같습니다.
계속 진행해 나가면서 최소 힙의 구조를 유지할 때까지 반복합니다.
최소 힙의 소스코드 구현(삭제 함수 추가 구현)
코드상에서 구현할 때에는 그림과 같이 맨 마지막 노드를 루트 노드에 직접 집어넣는 것은 필요가 없고, 비교를 계속 진행하여 들어갈 자리를 찾은 뒤, 찾았으면 그 자리에 마지막 노드 값을 집어 넣으면 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int delete(int *n){
int first, temp, parent, child;
first = heap[1];
temp = heap[(*n)--];
parent = 1;
child = 2;
while (child <= *n) {
if ((child < *n) && (heap[child] > heap[child + 1]))
child++;
if (temp <= heap[child])
break;
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = temp;
return first;
}
1
2
3
4
5
6
////main 함수 뒤에 이어서...
printf("\n\n최상위 노드 삭제(반환)값 : %d", delete(count));
printf("\n삭제 후 힙의 Level Order Traversal : ");
for (int i = 1; i <= count; i++) {
printf("%d ", heap[i]);
}
1
2
3
4
5
6
7
8
9
10
11
Min Heap 구현 - 숫자를 입력하세요.
*****숫자 입력(-1을 입력하면 입력 종료)*****
1
2
3
4
5
-1
>> Level Order Traversal : 1 2 3 4 5
>> 최상위 노드 삭제(반환)값 : 1
>>> 삭제 후 힙의 Level Order Traversal : 2 4 3 5
위의 삭제 코드에서 부등호 몇 개만 고치면 최대 힙의 삭제를 구현할 수 있습니다.
그리고 1부터 7까지 입력할 경우, 원래 힙의 Level order Traversal의 결과는 7 4 6 1 3 2 5 가 나오며, 최상위 노드를 삭제한 후의 힙의 Level order Traversal의 결과는 6 4 5 1 3 2 가 나오게 됩니다.