앞에서 자료구조 트리에 대한 기본적인 이론을 살펴본 적이 있습니다.

이러한 트리 구조를 기반으로 발전한 다양한 응용 트리 자료구조를 살펴보려고 합니다.
Heap, Trie, AVL Tree, Red-Black Tree, B-Tree 그리고 게임 AI에서 활용되는 Behavior Tree까지 순차적으로 학습하며 각각이 어떤 문제를 해결하기 위해 등장했는지 알아보겠습니다.

이번 글에서는 Heap을 살펴보겠습니다

🌲 1. Heap

힙은 가장 우선순위가 높은 값을 빠르게 꺼내기 위한 트리 구조입니다.

여기서 우선순위가 가장 높다는 건 꺼낼 때마다 항상 최댓값(또는 최솟값)이 나오도록 설계된 트리라는 뜻입니다

BST는 왼쪽 < 나 < 오른쪽 규칙이었다면, Heap은 대표적으오 2가지 규칙을 가집니다

🔖 1-1. Max Heap

부모가 자식보다 크거나 같은 트리

해당 트리를 보시면 Root인 90이 가장 큰 것을 알 수 있습니다

🔖 1-2 Min Heap

부모가 자식보다 작거나 같은 트리

Min Heap은 반대로 Root인 10이 가장 작은 값입니다.

🔖 1-3. 삽입(Insert)

🗃️ 삽입 과정

1️⃣ 새 값을 맨 마지막에 추가
2️⃣ 부모와 비교해서 크면 교환 → 이 과정을 Heapify Up 또는 Bubble Up 이라고 합니다
3️⃣ 부모보다 작거나 루트에 도달하면 멈춤

글로만 보면 이해를 할 수는 없으니 해당 힙으로 삽입 과정을 알아봅시다.

배열로 나타낸다면 아래와 같습니다.

[90, 70, 50, 30, 40]

여기에 100을 추가한다고 할 때 삽입 과정입니다.

🔖 1-4. 삭제(Delete)

Heap에서 삭제는 항상 루트(최댓값)만 삭제해. "지금 당장 가장 큰 값을 꺼내줘"가 Heap의 존재 이유거든.

❌ 삭제 과정

1️⃣ 루트 제거
2️⃣ 마지막 노드를 루트 자리로 이동
3️⃣ 자식 중 더 큰 값과 비교해서 작으면 교환 → 이 과정을 Heapify down 또는 Bubble down 이라고 합니다
4️⃣ 자식보다 크거나 리프에 도달하면 멈춤

마찬가지로 글로만 보면 이해를 할 수는 없으니 해당 힙으로 삭제 과정을 알아봅시다.

배열로 나타낸다면

[100, 70, 90, 30, 40, 50]

여기서 100을 삭제한다고 했을 때 삭제 과정입니다

🔖 1-5. 시간복잡도

루트만 보면 되니까 조회는 O(1), 삽입, 삭제는 트리 높이만큼만 이동하니까 O(log n)가 됩니다.

연산	시간 복잡도
삽입	O(log n)
삭제	O(log n)
최댓값/최솟값 조회	O(1)

🔖 1-6. Heap이 완전 이진 트리인 이유 2가지

✔️ 1-6-1. 높이를 낮게(logN) 유지

Heap에서 중요한 연산은 삽입과 삭제입니다.
둘 다 연산 시 부모 방향으로 이동하거나 자식 방향으로 반복해서 이동합니다
따라서 성능은 트리 높이에 비례할 수 밖에 없습니다.

🆚 완전 이진 트리 vs 편향 트리 비교

노드가 같은 7개라고 했을 때

완전 이진 트리의 경우

높이가 3이 되기 때문에 삽입/삭제 시 최대 3번까지 이동합니다.

편향 트리의 경우

높이가 7이 되기 때문에 삽입/삭제 시 최대 7번까지 이동합니다.

즉, 완전 이진 트리면 O(logN), 편향 트리의 경우 O(N)가 되는 거고 높이를 낮게 유지하는 게 곧 속도이기 때문에 Heap에 완전 이진 트리를 사용하는 겁니다

✔️ 1-6-2. 배열로 구현하기 위해

완전 이진 트리는 위에서 아래, 왼쪽에서 오른쪽 순서로 노드를 채우기 때문에 배열로 쉽게 구현이 가능합니다.

레벨 0:        90          → 인덱스 0
레벨 1:      70  50        → 인덱스 1, 2
레벨 2:    30  40  10      → 인덱스 3, 4, 5

해당 트리를 배열로 나타낸다면 아래와 같이 나타낼 수 있습니다

[90, 70, 50, 30, 40, 10]

그렇게 된다면 부모, 자식을 해당 계산으로 찾을 수 있습니다!

left  = index * 2 + 1;
right = index * 2 + 2;
parent = (index - 1) / 2;

계산식만 봤을 때는 이해하기 힘드니 예를 들어볼까요?

heap[0] = 90

이 친구의 왼쪽 자식은 index * 2 + 1를 적용하여 0 * 2 + 1 = 1로 계산한다면

heap[1] = 70

으로 나오는 것을 알 수 있습니다.


오른쪽 자식을 계산해보면 index * 2 + 2를 적용하여 0 * 2 + 2 = 2로 계산한다면

heap[2] = 50

으로 나오는 것을 알 수 있습니다.