힙 트리

최근 수정 시각:

파일:나무위키프로젝트.png
이 문서는 나무위키 동음이의어 개선 프로젝트에서 다루는 문서입니다.
해당 프로젝트 문서를 방문해 도움이 필요한 문서에 기여해 주세요!

파일:나무위키+유도.png
동음이의어 힙에 대해서는 볼기 문서를 참조하십시오.

Heap tree Hip tree
여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리. 짧게 힙(Heap)이라고 줄여서 부르기도 한다.


1. 정의2. 데이터 처리
2.1. 데이터 삽입2.2. 데이터 삭제
3. 응용 분야4. 코드
4.1. C++

1. 정의[편집]

파일:external/upload.wikimedia.org/Min-heap.png

영단어 힙(heap)은 '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻을 지니고 있다. 힙은 항상 완전 이진 트리[1]의 형태를 띄어야 하고, 부모의 값은 항상 자식(들)의 값보다 크거나(Max heap 최대 힙), 작아야(Min heap 최소 힙)하는 규칙이 있다. 따라서 루트노드에는 항상 데이터들 중 가장 큰 값(혹은 가장 작은 값)이 저장되어 있기 때문에, 최댓값(혹은 최솟값)을 O(1)O(1)안에 찾을 수 있다.

단순히 최댓값(최솟값)을 O(1)O(1)안에 찾기 위해서라면 "항상 완전 이진 트리의 형태여야 한다"는 조건을 만족시킬 필요는 없다. 완전 이진 트리를 사용하는 이유는 삽입/삭제의 속도 때문이다. 물론 '힙 트리'는 정의상 완전 이진 트리를 사용하는 트리다. 달리 다른 구조를 사용한다 해도 전혀 얻을게 없는 최적의 구조이기 때문.

2. 데이터 처리[편집]

데이터의 삽입과 삭제는 모두 O(logN)O(log N)이 소요된다.

2.1. 데이터 삽입[편집]

  1. 가장 끝의 자리에 노드를 삽입한다.

  2. 그 노드와 부모 노드를 서로 비교한다.

  3. 규칙에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다.

  4. 규칙에 맞을 때까지 3번 과정을 반복한다.


파일:external/www.cprogramming.com/heapadd.jpg

2.2. 데이터 삭제[편집]

최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있다.

  1. 루트 노드를 제거한다.

  2. 루트 자리에 가장 마지막 노드를 삽입한다.[2]

  3. 올라간 노드와 그의 자식 노드(들)와 비교한다.

  4. 조건에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환한다.

  • 최대 힙

    1. 부모보다 더 큰 자식이 없으면 교환하지 않고 끝낸다.

    2. 부모보다 더 큰 자식이 하나만 있으면 그 자식하고 교환하면 된다.

    3. 부모보다 더 큰 자식이 둘 있으면 자식들 중 큰 값과 교환한다.

  • 최소 힙

    1. 부모보다 더 작은 자식이 없으면 교환하지 않고 끝낸다.

    2. 부모보다 더 작은 자식이 하나만 있으면 그 자식하고 교환하면 된다.

    3. 부모보다 더 작은 자식이 둘 있으면 자식들 중 작은 값과 교환한다.

5. 조건을 만족할 때까지 4의 과정을 반복한다.


파일:external/www.cprogramming.com/heapremove.jpg

3. 응용 분야[편집]

힙의 형태를 보면 최대 힙의 경우 루트가 항상 최대값이고, 최소 힙의 경우 루트가 항상 최소값임을 알 수 있다.
이를 이용하여 우선순위 큐(priority queue)를 구현하거나, 힙 정렬(heap sort)을 만드는 등의 일을 할 수 있다.
또한 무손실 압축 알고리즘(?)인 허프만 코드도 힙의 구조를 기반으로 하고있다.

4. 코드[편집]

4.1. C++[편집]

최소 힙 기준으로 짜인 소스이다.

  • 삽입

void creheap(int *arr2, int key, int input) {
	arr2[key] = input;
	while (key > 1) {
		if (arr2[key] < arr2[key / 2]) {
			swap(arr2[key], arr2[key / 2]);
			key /= 2;
		}
		else break;
	}
}

  • 삭제
    루트 노드 삭제 후 힙의 마지막 데이터를 가져온 상태를 가정한다.

void delheap(int *arr3, int key, int heap_size) {
	int tmp, nextkey;
	while (heap_size >= key * 2) {
		if (key * 2 + 1 > heap_size && arr3[key * 2] < arr3[key]) {
			swap(arr3[key * 2], arr3[key]);
			key = key * 2;
		}
		else if (key * 2 + 1 > heap_size) break;
		else {
			if (arr3[key * 2] < arr3[key * 2 + 1]) {
				tmp = arr3[key * 2];
				nextkey = key * 2;
			}
			else {
				tmp = arr3[key * 2 + 1];
				nextkey = key * 2 + 1;
			}
			if (tmp < arr3[key]) swap(arr3[key], arr3[nextkey]);
			else break;
		}
	}
}


기타 다른 언어 코드는 추가바람.

[1] 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득 차있는 이진 트리[2] 이는 수정될 힙에서 중간에 빈 공간이 생기지 않게 하기 위함이다

분류