힙이란?
- 무엇인가 쌓아놓은 것과 비슷한 형태의 특정한 자료구조로 트리 중에서 완전 이진 트리의 형태를 가진다.
- 여러개의 값들 중에서 최대 값이나 최소 값을 빠르게 찾아내도록 만들어진 자료구조이다.
- 우선순위 큐를 구현 할 때 힙을 사용한다.
우선순위 큐?
우선순위 큐는 우선순위가 높은 순서로 먼저 나가게 되는 큐로 대표적으로 최단경로 알고리즘을 구현할때 사용한다.
완전 이진 트리는 트리에서 설명하였듯이 이진 트리 중에서 앞에서부터 중간에 빈 노드없이 차례대로 노드를 채우고 있는 형태를 말한다.
힙(heap)의 종류
힙은 최대 힙과 최소 힙으로 나뉜다. 그림과 함께 살펴보자.
최대힙(max heap)
부모노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리를 말한다.
항상 부모노드의 키값이 자식 노드의 키값보다 크거나 같아야한다.(부모노드 >= 자식노드)
오른쪽 그림의 경우 부모노드가 자식노드보다 작은 경우가 존재하기 때문에 최대힙, 즉 힙을 만족하지 못한다.
최소힙(min heap)
부모노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리를 말한다.
최대힙과 반대로 항상 부모노드의 키값이 자식 노드의 작거나 같아야한다.(부모노드 <= 자식노드)
그림을 보면 둘다 부모 노드가 자식노드보다 작거나 같은 것을 확인 할 수 있지만 오른쪽 그림의 경우 완전 이진 트리를 만족하지 못하여 최소힙이라고 할 수 없다.
참고) 느슨한 정렬?
힙은 레벨에 따라 일부 정렬되어 있어 느슨한 정렬을 유지 한다.
평균적으로 큰값이 상위 레벨에 있고 작은 값이 하위레벨에 존재한다.
힙(heap)의 구현
힙은 배열을 사용해서 구현할 수 있다. 각 노드를 위에서부터 순서대로 번호(index)를 부여하여 저장한다.
배열의 첫번째 인덱스인 0은 구현을 쉽게 하기위해 사용하지 않는다.
위를 바탕으로 기존의 트리에서 접근하는 방식과 같이 부모 자식간의 관계를 인덱스로 정의 할 수 있다.
왼쪽 자식 인덱스 = (부모의 인덱스) * 2
오른쪽 자식 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식노드의 인덱스) / 2
C언어 코드
힙 정의
힙의 전체 요소의 크기와 배열을 정의 한다.
#define MAX_ELEMENT 200
typedef struct {
int key;
} element;
typedef struct {
element heap[MAX_ELEMENT];
int heap_size;
} HeapType;힙 삽입
- 삽입하고자 하는 원소를 맨 뒤에 삽입 한다.
- 최소힙 또는 최대힙을 만족하도록 위치를 조정한다.
최대 힙의 경우 삽입할 노드와 부모노드를 비교하여 삽입 노드가 크면 삽입노드와 부모 노드의 위치를 변경한다.
아래는 최대 힙으로 구현한 삽입 함수이다. 최소힙은 비교과정을 작은 경우로 변경하면 된다.
void insert_max_heap(HeapType* h, element item)
{
int i;
i = ++(h->heap_size); // 삽입된 노드의 인덱스를 의미한다.
// 삽입노드가 부모노드보다 크면 한 레벨 위로 올라간다.
while((i != 1) && (item.key > h->heap[i/2].key){
h->heap[i] = h->heap[i/2]; // 부모노드를 자식 노드로 내린다.
i /= 2; // 레벨 위로 가기
}
h->heap[i] = item; // 올바른 위치에 삽입 노드를 저장
}힙 삭제
- 삭제할 노드(1번째 인덱스의 값)을 저장 한다.
- 마지막 위치의 노드를 1번째 인덱스의 위치에 교체한다.
- 최소힙 또는 최대힙을 만족하도록 위치를 조정한다.
아래는 최대 힙으로 작성한 힙 삭제 함수이다. 삭제 노드를 반환한다.
element delete_max_heap(HeapType* h)
{
int parent, child;
element item, temp;
item = h->heap[1]; // 삭제할 노드(반환할 노드) 저장
temp = h->heap[(h->heap_size)--]; // 마지막 노드
parent = 1;
child = 2;
while(child <= h->heap_size){
// 더 큰 자식 노드와 비교하기 위해 자식노드 찾기
if((child < h->heap_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; // 삭제된 노드 반환
} 마무리
힙은 삽입 삭제 할 때 최악의 경우 전체 힙의 높이만큼 비교하기 때문에 노드의 개수가 n일 경우 O(log₂n)의 복잡도를 가진다.
힙을 사용하면 힙에 원소를 삽입 후 하나씩 값을 가져오면 정렬된 값을 얻을 수 있다.
정렬시에는 (전체 원소를 삽입하는 연산 * 비교연산)으로 O(nlog₂n)의 복잡도를 가진다.
최단 경로 문제와 같이 우선순위 큐를 사용하는 문제에서 활용되기 때문에 어떤식으로 동작하는지 기억해두자.
📕 참고 문헌
다음의 문헌을 참고했습니다.
C언어로 쉽게 풀어쓴 자료구조 [ 개정3판 ]
천인국, 공용해, 하상호 저 | 생능출판사 | 2021년 08월 20일
[자료구조] 힙(heap)이란 - heejeong Kwon 10 May 2018
