힙 트리

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

1. 정의

---

<파이썬 알고리즘 인터뷰> p.447, 책만, 2020
영단어 힙(heap)은 '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻을 지니고 있다. 힙은 항상 완전 이진 트리[1]의 형태를 띠어야 하고, 부모의 값은 항상 자식(들)의 값보다 크거나(Max heap 최대 힙), 작아야(Min heap 최소 힙)하는 규칙이 있다. 따라서 루트노드에는 항상 데이터들 중 가장 큰 값(혹은 가장 작은 값)이 저장되어 있기 때문에, 최댓값(혹은 최솟값)을 $$O(1)$$안에 찾을 수 있다.
단순히 최댓값(최솟값)을 $$O(1)$$안에 찾기 위해서라면 "항상 완전 이진 트리의 형태여야 한다"는 조건을 만족시킬 필요는 없다. [2] 완전 이진 트리를 사용하는 이유는 삽입/삭제의 속도 때문이다. 물론 '힙 트리'는 정의상 완전 이진 트리를 사용하는 트리다. 달리 다른 구조를 사용한다 해도 전혀 얻을게 없는 최적의 구조이기 때문.

2. 데이터 처리

---

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

2.1. 데이터 삽입

---

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

<파이썬 알고리즘 인터뷰> p.450, 책만, 2020

2.2. 데이터 삭제

---

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

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

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

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

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

<파이썬 알고리즘 인터뷰> p.451, 책만, 2020

3. 표현

---

<파이썬 알고리즘 인터뷰> p.407, 책만, 2020
이진 힙은 완전 이진 트리(Complete Binary Tree)로서, 배열로 표현하기 매우 좋은 구조다. 높이 순서대로 순회하면 모든 노드를 배열에 낭비 없이 배치할 수 있기 때문이다. 그림처럼 완전 이진 트리는 배열에 빈틈없이 배치가 가능하며, 대개 트리의 배열 표현의 경우 계산을 편하게 하기 위해 인덱스는 1부터 사용한다.
해당 노드의 인덱스를 알면 깊이가 얼마인지, 부모와 자식 노드가 배열 어디에 위치하는 지 바로 알아낼 수 있다. 깊이는 1, 2, 4, 8, ... 순으로 2배씩 증가하며, 인덱스는 1부터 시작했기 때문에 부모/자식 노드의 위치는 각각 부모 $$\lfloor\frac{i-1}{2}\rfloor$$ , 왼쪽 자식 $$2i$$, 오른쪽 자식 $$2i+1$$의 간단한 수식으로 계산할 수 있다. 이처럼 해당되는 배열의 인덱스를 금방 찾아낼 수 있다. 물론 꼭 완전 이진 형태가 아니어도 비어있는 위치는 얼마든지 널(Null)로 표현할 수 있기 때문에, 사실상 모든 트리는 배열로 표현이 가능하다.

4. 응용 분야

---

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

5. 코드

---

5.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] 극단적으로 말해서, 최댓값/최솟값을 항상 헤드에 두고, 나머지 데이터는 비교하든 말든 그냥 뒤에 쭉 이어붙인 연결 리스트로도 최댓값/최솟값을 상수 시간 내에 찾을 수 있다.

[3] 이는 수정될 힙에서 중간에 빈 공간이 생기지 않게 하기 위함이다