힙 (Heap) or 이진 힙(binary heap) 알아보기
힙(heap)은 이진 힙(binary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조입니다.
힙은 다음과 같은 속성을 가지고 있습니다.
- 완전 이진트리(Complete Binary Tree) 이다.
- 부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다.
- 키값 대소관계는 오로지 부모자식 간에만 성립되며 형제사이에는 대소관계가 정해지지 않음.
힙의 종류
힙에는 두가지 종류(최대 힙, 최소 힙)가 있습니다.
1. 최대 힙 (Max Heap)
- 부모 키값이 자식노드 키값보다 큰 힙
- Key(parent) ≥ Key(child)
- 가장 큰 값이 루트노드에 있음
2. 최소 힙 (Min Heap)
- 부모 키값이 자식노드 키값보다 작은 힙
- Key(parent) ≤ Key(child)
- 가장 작은 값이 루트노드에 있음
힙 표현
힙은 완전 이진트리입니다. 힙은 일반적으로 배열로 표현합니다.
개발 편의성과 가독성 때문에 배열 인덱스 1부터 사용합니다.
루트 노드의 인덱스 i가 1인 경우 다음과 같은 속성이 있습니다.
- 노드 i의 부모노드 인덱스 : \( \lfloor i/2 \rfloor \)
- 노드 i의 왼쪽 자식 노드 인덱스 : 2*i
- 노드 i의 오른쪽 자식 노드 인덱스 : 2*i + 1
힙 연산
최대 힙을 예로 설명하겠습니다.
힙에 있는 요소수를 나타내는 size 변수는 전역변수라고 가정하겠습니다.
Heapify
heapify는 이진트리에서 힙 속성을 유지하는 작업을 합니다. 위에서 아래로 내려가면서 작업을 합니다.
max heap에서 heapify의 작업은 다음과 같습니다.
- 요소 값과 자식 노드 값을 비교합니다.
- 만약 자식 노드 값이 크다면 왼쪽 오른쪽 자식 중 가장 큰 값으로 교환합니다.
- 힙 속성이 유지 될 때까지 1,2번 과정을 반복합니다.
다음 그림은 값이 8인 노드에 대해 heapify를 수행하는 예입니다.
Step 1. 첫 번째 노드 값(8)이 자식보다 작으므로 자식 중 가장 큰 오른쪽 자식 값(20)과 교환합니다.
Step 2. 값이 8인 노드에서 heapify를 다시 시작합니다. 8이 왼쪽 자식 노드 13보다 작기 때문에 교환합니다.
이제 8이 leaf node이므로 heapify를 추가로 호출해도 힙 구조에 영향을 주지 않습니다.
구현
void max_heapify (int arr[], int i)
{
int largest = i;
int left = 2*i //left child
int right = 2*i +1 //right child
// 현재 요소 i와 자식 노드의 값을 비교
if(left <= size && arr[left] > arr[i] )
largest = left;
if(right <= size && arr[right] > arr[largest] )
largest = right;
// 자식 노드의 값이 더 크다면 교환하고 교환된 자식 노드부터 heapify 진행
if(largest != i ) {
swap (arr[i] , arr[largest]);
max_heapify (h, largest);
}
}시간 복잡도: O(logN)
Build heap
완전 이진트리를 heap구조로 만드는 작업을 합니다.
배열로 표현된 힙은 n/2+1부터 n까지 leaf node라는 속성이 있습니다. (루트 노드가 1인 경우)
leaf node를 제외한 나머지 노드(1~n/2)에 heapify 를 수행하면 heap 구조로 build 할 수 있습니다.
max heap으로 build하는 작업은 다음과 같습니다.
- leaf node를 제외한 나머지 노드중 마지막 노드(n/2)부터 루트 노드(1)까지 차례로 max_heapify를 수행합니다.
다음 그림은 build heap을 수행하는 예입니다.
구현
void build_maxheap (int arr[]) {
int i = 0;
for(i = size/2; i >=1; i--) {
max_heapify(arr, i);
}
}시간 복잡도: O(n)
Peek
heap에 최대 요소를 반환하는 작업을 합니다.
max heap에서 최대 값은 항상 루트에 있으므로 루트 값을 반환합니다.
구현
int peek (int arr[]) {
return arr[1];
}시간 복잡도: O(1)
Extract
extract는 heap에 최대 요소를 추출하는 작업을 합니다.
max heap에서 extract의 작업은 다음과 같습니다.
- heap의 최대 요소는 루트 노드에 있기 때문에 루트 노드의 값을 추출합니다.
- heap 마지막 요소를 루트 노드에 배치합니다.
- 마지막 요소를 루트 노드에 배치하면 heap 속성을 위배할 수 있으므로 루트 노드부터 max_heapify를 수행합니다.
다음 그림은 extract를 수행하는 예입니다.
Step 1. 루트 노드 값(20)을 추출합니다.
Step 2. heap 마지막 요소(13)를 루트 노드에 배치합니다.
Step 3. 루트 노드부터 hepify를 수행합니다.
구현
int extract_max (int arr[]) {
if(size == 0) {
printf("empty\n");
}
// 루트 노드 값을 리턴값에 저장한 뒤, 마지막 요소를 루트노드에 배치함
int max = arr[1];
arr[1] = arr[size];
size --;
// 루트 노드부터 heapify 수행
max_heapify(arr, 1);
return max;
}시간 복잡도: O(logN)
Increase Value
Increase value는 max heap에서 사용하는 작업으로 어느 노드의 값을 증가시키는 작업을 합니다.
(min heap에서는 decrease value를 사용합니다.)
만약 heap 속성을 위배하는 경우 부모 노드가 더 큰 값이 될 때까지 부모 노드와 값을 바꾸는 작업을 합니다.
heapify작업은 필요가 없습니다.
이유는 max heap 구조에서는 노드의 값을 증가시켜도 항상 자식 노드보다 크다는 것이 보장되기 때문입니다.
반대로 min heap 구조에서는 노드의 값을 감소시키면 항상 자식 노드보다 작다는 것이 보장됩니다.
increase value작업은 다음과 같습니다.
- 어느 노드의 값을 증가시킵니다.
- 부모 노드와 비교하여 heap속성을 위배하는 경우 부모 노드와 값을 바꿉니다.
- 힙 속성이 유지될 때까지 2번 작업을 반복합니다.
다음 그림은 increase value를 수행하는 예입니다.
Step 1. 값이 5인 노드를 30으로 증가시킵니다.
Step 2. 부모 노드와 값을 비교합니다. 부모 노드가 더 작아 heap 속성을 위배하므로 부모 노드와 값을 바꿉니다.
Step 3. 값이 30인 노드에서 다시 부모 노드와 값을 비교합니다.
- 부모 노드가 더 작아 heap 속성을 위배하므로 부모 노드와 값을 바꿉니다.
Step 4. 더 이상 heap 속성을 위배하지 않기 때문에 종료합니다.
구현
// i index에 있는 노드 값을 val로 변경함.
void increase_value (int arr[], int i, int val) {
// 변경하려는 값이 현재 값보다 작으면 안됨.
if (val < arr[i]) {
printf("New value is less then current value, can't be inserted\n");
return;
}
// 현재 값을 val값으로 변경
arr[i] = val;
// 부모 노드가 더 작다면 교환하고 부모 노드부터 다시 비교, 힙속성을 유지할 때까지 반복함.
while(i > 1 && arr[i/2] < arr[i]) {
swap(arr[i/2], arr[i]);
i = i/2;
}
}시간 복잡도: O(logN)
Insert
힙에 요소를 삽입하는 작업은 다음과 같습니다.
- 힙의 끝에 최솟값을 삽입합니다.
- increase value 함수를 호출하여 추가된 값을 삽입할 값으로 증가시키고 힙 속성을 유지합니다.
다음 그림은 요소 17을 삽입하는 예입니다.
step 1. 힙의 끝에 최솟값을 삽입합니다.
step 2. increase value 함수를 호출합니다.
- 추가된 최소값을 17로 증가시킵니다.
- 부모 노드와 값을 비교합니다. 부모 노드값이 더 작기 때문에 교환합니다. (힙속성 위배)
step3. 값이 17인 노드와 부모 노드를 비교합니다. 힙 속성을 위배하지 않으므로 종료합니다.
구현
void insert_key(int arr[], int val)
{
int last = 0;
if (size == MAX_LEN) { // 배열에 공간이 없으면 실패
printf("Overflow: Could not insertKey\n");
}
// 힙 끝에 최소값 삽입.
size ++;
last = size;
arr[last] = INT_MIN;
// 마지막 요소값을 val로 증가 시키고 heap 속성을 유지하는 작업을 함.
increase_value(arr, last, val);
}시간 복잡도: O(logN)
Delete
힙에서 요소를 삭제하는 작업은 다음과 같습니다.
- increase value를 수행하여 삭제할 요소를 max 값으로 증가시키고 루트 노드에 위치시킵니다.
- extract를 수행하여 루트 노드에 값을 추출합니다.
다음 그림은 요소 15를 삭제하는 예입니다.
step1~2. increase value를 수행합니다.
- step1. 값 15를 MAX값으로 증가시킵니다.
- step2. max 값을 루트 노드에 위치시킵니다.
step3~4. extract를 수행합니다.
- step3. 힙에 마지막 요소 13을 루트로 이동시킵니다.
- step4. 루트 노드부터 max_heapify를 수행합니다.
구현
//i index에 위치한 요소를 삭제
void delete_key (int arr[], int i) {
increase_value(arr, i, INT_MAX);
extract_max(h);
}시간 복잡도: O(logN)
사용 사례
- 우선순위 큐
- Dijkstra 알고리즘
- 힙 정렬
