힙 트리

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

1 정의

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

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

2 데이터 처리

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

2.1 데이터 삽입

1. 가장 끝의 자리에 노드를 삽입한다.
2. 그 노드와 부모 노드를 서로 비교한다.
3. 규칙에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다.
4. 규칙에 맞을 때까지 3번 과정을 반복한다.

2.2 데이터 삭제

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

1. 루트 노드를 제거한다.
2. 루트 자리에 가장 마지막 노드를 삽입한다.
3. 올라간 노드와 그의 자식 노드(들)와 비교한다.
4. 조건에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환한다.

• 최대 힙
  1. 부모보다 더 큰 자식이 없으면 교환하지 않고 끝낸다.
  2. 부모보다 더 큰 자식이 하나만 있으면 그 자식하고 교환하면 된다.
  3. 부모보다 더 큰 자식이 둘 있으면 자식들 중 큰 값과 교환한다.

• 최소 힙
  1. 부모보다 더 작은 자식이 없으면 교환하지 않고 끝낸다.
  2. 부모보다 더 작은 자식이 하나만 있으면 그 자식하고 교환하면 된다.
  3. 부모보다 더 작은자식이 둘 있으면 자식들 중 작은 값과 교환한다.

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

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] 

• 삭제

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

!-- HTML generated using hilite.me -->

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 span style="color: #333333"*/span span style="color: #0000DD; font-weight: bold"2/span], arr3[key]);
key span style="color: #333333"=/span key span style="color: #333333"*/span span style="color: #0000DD; font-weight: bold"2/span;
}
span style="color: #008800; font-weight: bold"else/span span style="color: #008800; font-weight: bold"if/span (key span style="color: #333333"*/span span style="color: #0000DD; font-weight: bold"2/span span style="color: #333333"+/span span style="color: #0000DD; font-weight: bold"1/span span style="color: #333333"> heap_size) break;
else {

if (arr3[key * 2] 

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