히프(heap)란?
히프는 우선순위 큐를 구현하는 데 자주 사용된다. 우선순위 큐에서는 우선순위가 가장 높은(또는 낮은) 원소를 먼저 삭제한다.
히프에 대한 설명을 하기 전에 최대 트리와 최소 트리에 대한 설명을 먼저 진행한다.
최대 트리 란 각 노드의 키 값이 그 자식의 키 값보다 작지 않은 트리이며,
최소 트리 란 각 노드의 키 값이 그 자식의 키 값보다 크지 않은 트리를 말한다.
여기서 최대 히프 란 최대 트리이면서 완전 이진트리이며, 최소 히프 란 최소 트리이면서 완전 이진트리를 의미한다.
이러한 최대 히프 및 최소 히프에서는 부모를 쉽게 찾아 삽입이 가능하다.
히프의 생성은 C를 통하여 다음과 같이 구현한다.1
2
3
4
5
6
7
8
9#define MAX_ELEMENTS 200
#define HEAP_FULL(n) (n==MAX_ELEMENTS-1)
#define HEAP_EMPTY(n) (!n)
typedef struct{
int key;
} element;
element heap[MAX_ELEMENTS];
int n=0;
최대 히프에서의 삽입
최대 히프에서 원소를 삽입하는 경우 추가되는 원소가 가장 아래부터 루트 쪽으로 올라가는 bubbling up 기법이 사용된다.
다음은 최대 히프에서의 원소의 삽입을 구현한 C 프로그램이다.
1 | #include <stdio.h> |
최대 히프에서의 삭제
최대 히프에서 원소의 삭제는 제일 위에서 이루어 진다.
먼저, 키값이 가장 큰 원소를 삭제하고 마지막 원소를 제거하고 두 자식 노드중 큰 값이 위로 올라가고 아래를 메꾸는 방식으로 진행된다.
최대 히프의 삭제를 구현한 프로그램은 다음과 같다.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24element pop(int *n)
{
int parent, child;
element item, temp;
if(HEAP_EMPTY(*n)){
fprintf(stderr, "The heap is empty\n");
exit(EXIT_FAILURE);
}
item=heap[1];
temp = heap[(*n)--];
parent = 1;
child = 2;
while(child <= *n){
if((child < *n) && (heap[child].key < heap[child+1].key))
child++;
if(temp.key > heap[child].key) break;
heap[parent] = heap[child];
parent = child;
child *= 2;
}
heap[parent] = temp;
return item;
}
B - 히프
B - 히프란 최소 트리의 집합이다.
Comments