힙(Heap)이란?
- 완전이진트리의 일종이다.
- 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다.
- 힙은 중복된 값을 허용한다.
- Max Heap 은 가장 큰 값을 빠르게 찾기 위한 것이고 Min Heap 가장 작은 값을 빠르게 찾기 위한 것이다.
완전이진트리가 무엇인지 모르겠다면 다음을 참고하자.
Max Heap(최대 힙)
- Max Heap 은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다.
- 부모노드의 key >= 자식 노드의 key
Min Heap(최소 힙)
- Min Heap 은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리이다.
- 부모노드의 key <= 자식 노드의 key
Heap 구현
Heap은 배열을 통해 쉽게 구현할 수 있다. 이진 탐색 트리의 경우에는 연결리스트로 구현하였는데, Heap은 배열로 구현하는 이유가 무엇일까? 그 이유는 Heap이 완전 이진 트리이기 때문이다. 완전 이진 트리의 특성상 왼쪽부터 오른쪽으로 차곡차곡 노드가 저장되므로 배열의 구조를 사용할 수 있게 된다. 아래 그림을 보면 이해가 빠를 것이다.
위 그림은 Max Heap을 배열로 표현한 것이다. 여기서 특이한 점은 0번 index를 사용하지 않는다는 것인데, 이는 구현을 쉽게 하기 위해서이다. index를 통해 노드를 접근할 수 있는데, 이를 다음과 같이 정리 할 수 있다.
- 부모노드의 index = (자식노드의 index) / 2 (ex : index 4번 노드의 부모노드 : index 2번 노드)
- 왼쪽 자식 노드의 index = (부모노드의 index)*2 (ex : index 3번 노드의 왼쪽 자식 노드 : index 6번 노드)
- 오른쪽 자식 노드의 index = (부모노드의 index)*2 + 1 (ex : index 3번 노드의 오른쪽 자식 노드 : index 7번노드)
타입 정의 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
|
#include <stdio.h>
#define MAX_SIZE 100 // Heap 의 최대 원소 개수
typedef struct{ // Heap 의 노드
int key; // Heap 의 key
/* 여기에 데이터 추가 가능 ex) int data */
}element;
typedef struct{ // Heap 자료구조
element heap[MAX_SIZE];
int size;
};
|
cs |
Heap 의 삽입
힙의 삽입은 다음과 같은 과정을 거친다.
1. 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다. ( = 배열의 마지막에 원소를 추가한다. )
2. 새로운 노드를 부모 노드와 비교해서 교환해야 한다면 힙의 성질을 만족 할 때까지 교환한다.
예를 들어 위의 Max Heap에 새로운 노드(key=8)를 추가한다고 하자.
첫 번째로 배열의 가장 마지막 위치에 새로운 원소 8을 추가한다.
두 번째로 부모노드인 index 4번 노드와 키 값을 비교한다. 이 때 자식노드인 index 8번 노드가 키 값이 더 크므로(8>4) 부모노드와 위치를 교환한다.
마지막으로 부모노드인 index 2번 노드와 키 값을 비교한다. 이 때 자식노드인 index 4번 노드가 키 값이 더 크므로(8>7) 부모노드와 위치를 교환한다. 이렇게 하면 Max Heap 의 성질을 만족하게 되고 삽입 과정이 종료된다.
Max Heap 을 예로 들었다. Min Heap 은 반대로 부모노드가 자식노드보다 작도록 교환하면 된다.
Heap의 삽입 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void max_heap_insert(Heap* h, element item){
int i;
i = ++(h->size); // 마지막 위치(마지막 원소의 index+1)
/* 루트노드가 아니고, 삽입할 값이 적절한 위치를 찾을 때까지*/
while( (i != 1) && (item.key > h->heap[i/2].key) ){
h->heap[i] = h->heap[i/2]; // 자식 노드와 부모노드 교환
i /= 2; // 한 레벨 위로 올라감
}
h->heap[i] = item; // 새로운 노드 삽입
}
|
cs |
Heap 의 삭제
Heap 에서의 삭제는 루트 노드를 삭제하고 반환한다는 뜻이다.
- Max Heap 에서의 삭제는 가장 큰 키 값을 가진 노드(root node)를 삭제하고 반환한다는 뜻이다.
- Min Heap 에서의 삭제는 가장 작은 키 값을 가진 노드(root node)를 삭제하고 반환한다는 뜻이다.
따라서 Heap에서의 삭제는 다음과 같은 과정을 거친다
1. 루트노드를 삭제한다. ( 나중에 값을 반환해야 하므로 따로 저장해놓는다)
2. 삭제된 루트 노드의 위치에 힙의 가장 마지막 노드를 가져온다.
3. 힙의 조건에 맞게 위치를 재설정한다. ( 이것을 heapify 라고 한다 )
그림을 보며 이해해보자. 여기서는 Max Heap 을 예시로 한다.
1. 루트노드를 삭제한다. ( 나중에 값을 반환해야 하므로 따로 저장해놓는다)
2. 삭제된 루트 노드의 위치에 힙의 가장 마지막 노드를 가져온다.
3. 힙의 조건에 맞게 위치를 재설정한다. (heapify)
이때 주의 할 점은 비교할 노드보다 큰 자식 노드가 2개 있을 때, 더 큰 값을 가진 자식 노드와 교환해야 한다는 것이다.
따라서 위에서는 index 1번 노드와 index 2번 노드가 교환되게 된다. ( 8>6 )
3. 힙의 조건에 맞게 위치를 재설정한다. (heapify)
마찬가지로 힙의 조건에 맞게 위치를 재설정하면 된다. 위와 같은 과정을 거치면 삭제가 완료된다.
Max Heap 의 조건을 만족하는 것을 확인 할 수 있다.
Heap의 삭제 소스코드
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
|
element max_heap_delete(Heap* h){
int parent, child;
element item, temp;
item = h->heap[1]; // 반환할 노드 저장
temp = h->heap[(h->size)--]; // 마지막 노드 temp 에 저장, 사이즈 1감소
parent = 1;
child = 2;
while(child <= h->size){
/* 왼쪽 자식 노드와 오른쪽 자식 노드 중 더 큰 자식 노드*/
if( (child < h->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];
/* 한 레벨 아래로 이동 */
parent = child;
child *= 2;
}
/* 마지막 노드를 재설정한 위치에 삽입 */
h->heap[parent] = temp;
/* 최댓값 노드 반환 */
return item;
}
|
cs |
전체 소스코드
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#include <stdio.h>
#define MAX_SIZE 100 // Heap 의 최대 원소 개수
typedef struct{ // Heap 의 노드
int key; // Heap 의 key
/* 여기에 데이터 추가 가능 ex) int data */
}element;
typedef struct{ // Heap 자료구조
element heap[MAX_SIZE];
int size;
}Heap;
void max_heap_insert(Heap* h, element item){
int i;
i = ++(h->size); // 마지막 위치(마지막 원소의 index+1)
/* 루트노드가 아니고, 삽입할 값이 적절한 위치를 찾을 때까지*/
while( (i != 1) && (item.key > h->heap[i/2].key) ){
h->heap[i] = h->heap[i/2]; // 자식 노드와 부모노드 교환
i /= 2; // 한 레벨 위로 올라감
}
h->heap[i] = item; // 새로운 노드 삽입
}
element max_heap_delete(Heap* h){
int parent, child;
element item, temp;
item = h->heap[1]; // 반환할 노드 저장
temp = h->heap[(h->size)--]; // 마지막 노드 temp 에 저장, 사이즈 1감소
parent = 1;
child = 2;
while(child <= h->size){
/* 왼쪽 자식 노드와 오른쪽 자식 노드 중 더 큰 자식 노드*/
if( (child < h->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];
/* 한 레벨 아래로 이동 */
parent = child;
child *= 2;
}
/* 마지막 노드를 재설정한 위치에 삽입 */
h->heap[parent] = temp;
/* 최댓값 노드 반환 */
return item;
}
int main(){
Heap max_heap;
element item;
item.key = 9;
max_heap_insert(&max_heap, item);
item.key = 7;
max_heap_insert(&max_heap, item);
item.key = 6;
max_heap_insert(&max_heap, item);
item.key = 4;
max_heap_insert(&max_heap, item);
item.key = 5;
max_heap_insert(&max_heap, item);
item.key = 1;
max_heap_insert(&max_heap, item);
item.key = 3;
max_heap_insert(&max_heap, item);
item.key = 8;
max_heap_insert(&max_heap, item);
while(max_heap.size > 0){
item = max_heap_delete(&max_heap);
printf("%d ", item.key);
}
return 0;
}
|
cs |
실행결과
'Computer Science > [자료구조]' 카테고리의 다른 글
[자료구조] 해시 테이블(Hash Table) 이란? , 해시 알고리즘 , 해시 함수 (0) | 2021.07.26 |
---|---|
[자료구조] 그래프(Graph)의 개념과 이해, 용어 | 인접행렬 vs 인접리스트 그래프 구현 (3) | 2021.07.22 |
[자료구조] 이진탐색트리(Binary Search Tree)의 개념, 이해 | C언어 이진탐색트리 구현 (4) | 2021.07.20 |
[자료구조] 트리의 순회, 중위 순회, 전위 순회, 후위 순회 | C언어 트리 순회 구현 (4) | 2021.07.19 |
[자료구조] 트리(Tree)의 개념, 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐색트리 (6) | 2021.07.16 |