[Java]자료구조 - 힙 트리(Heap Tree)

이전에 자료구조에 대한 글을 올리면서 트리에 대해 다룬 적이 있다.

 

2022.07.26 - [Development/Java] - [Java]자료구조 - Tree

[Java]자료구조 - Tree

그리고 최근 우선순위 큐에 대해 다루면서 내부적으로 O(log N)의 힙(Heap)을 사용한다고 언급했었는데,

 

2022.09.23 - [Development/Java] - [Java]우선순위 큐(Priority Queue) 튜토리얼

[Java]우선순위 큐(Priority Queue) 튜토리얼

이번 글에서는 트리구조 중 특별한 케이스이며 우선순위 큐 구현에 필요한 힙 트리(Heap Tree) 구조에 대해 알아보겠다.

 

Heap Tree

 

힙(Heap)은 더미, 쌓아 올리다 등의 뜻을 가지고 있는 영어단어이다.

 

여기서 힙 트리(Heap Tree)란 규칙을 가지고 쌓아 올려진 트리구조라는 것을 유추할 수 있는데,

 

구체적으로는 주어진 값 중에서 최댓값이나 최솟값을 빠르게(O(1)의 속도로) 찾기 위한 규칙을 지니고 있다.

 

규칙들은 생각보다 간단한 편이다. 하나씩 알아보자.

 

Complete Binary Tree

 

힙 트리는 기본적으로 완전 이진트리(Complete Binary Tree)의 형태를 띠어야 한다.

 

복습하자면 완전 이진트리란 루트에서 시작해 위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 채워나간 트리를 뜻한다.

 

덜 직관적인 표현으로는 마지막 레벨을 제외한 노드가 가득 차있어야 하고, 마지막 레벨의 노드는 왼쪽이 전부 차 있어야 한다.

 

사실 최댓값이나 최솟값을 O(1)의 속도로 찾아내려면 항상 완전 이진트리 형태를 가질 필요는 없지만,

 

데이터 삽입/삭제 속도(O(log N))를 유지하기 위해 존재하는 규칙이다.

 

Min Heap, Max Heap

 

최솟값을 찾는 Min Heap의 경우 부모 노드의 값은 항상 자식 노드의 값보다 작아야 하며,

 

최댓값을 찾는 Max Heap의 경우 부모 노드의 값이 항상 자식 노드의 값보다 커야 한다.

 

위와 같은 성질 때문에 일단 정렬이 끝난 힙 트리의 경우 최대, 최솟값을 O(1)의 속도로 찾아낼 수 있게 된다.

 

이어지는 글에선 우선순위 큐의 기본 설정인 오름차순(Min Heap)을 기준으로 설명하겠다.

 

Data Insertion

 

새로운 데이터를 삽입하는 방법은 다음의 순서를 따른다.

 

1. 가장 끝 자리에 노드 삽입
2. 삽입한 노드와 부모 노드 비교
3. 조건이 맞으면(Min Heap의 경우 부모 노드가 더 크면) 위치 교환
4. 더 이상 교환할 수 없을 때까지 교환 반복

 

Data Deletion

 

정렬된 힙 트리의 데이터 삭제는 루트 노드의 경우만 가능하며 아래의 순서를 따른다.

 

1. 루트 노드 제거
2. 가장 마지막 자리의 노드를 루트 자리로 이동
3. 자식 노드와 비교
   
   
   1. (Min Heap의 경우) 작은 자식 노드가 없으면 교환하지 않고 끝낸다.
   2. 부모보다 작은 자식이 하나만 있으면 그 노드와 교환한다.
   3. 부모보다 작은 자식이 둘 있으면 둘 중 작은 값을 가진 노드와 교환한다.
4. 더 이상 교환할 수 없을 때까지 반복

 

Heap Tree ↔ Array

 

완전 이진트리 형태를 가지고 있는 힙 트리는 배열로 구현하는 것이 편리하고 또 언제나 가능하다.

 

사실 모든 트리구조는 배열로 변환할 수 있지만, 완전 이진트리의 경우 빈틈없이 배치가 가능하다는 것이 특징이다.

 

배열의 0번 요소를 비워두고 1번부터 노드와 매치해서 채워둔 모습이다.

 

노드 간의 관계는 화살표로 나타냈으며, 이와 같이 깔끔하게 배열할 수 있기 때문에

 

해당 노드의 인덱스를 알면 깊이와 부모/자식 노드의 배열상 위치를 바로 알아낼 수 있다.

 

Min-Max Heap

 

이름대로 최소 힙과 최대 힙의 장점을 합쳐놓은 독특한 구조를 가지고 있다.

 

Min 레벨의 값은 해당 노드의 서브 트리 중에서 최솟값을 갖고,

 

Max 레벨의 값은 해당 노드의 서브 트리 중에서 최댓값을 갖는다.

 

루트 노드는 Min 레벨에 위치한다.

 

데이터의 삽입은 위의 힙 정렬과 같으며 삭제 역시 루트를 지우고 규칙에 따라 나머지를 배열하는 식이다.

 

그러므로 Min-Max Heap에서 루트 노드를 계속해서 지우면 Min Heap으로,

 

루트의 자식 노드 중 큰 값을 계속해서 지우면 Max Heap으로 기능하게 되는 것이다.

 

또한 데이터 삽입 및 정렬에는 O(log N)이 걸리며

 

최댓값과 최솟값을 찾는 데에는 O(1)의 시간이 소요된다.

 

즉, 두 힙의 장점을 완벽히 합쳐놓은 것이나 다름이 없다.

 

내용이 길어져 힙 트리의 구현은 다른 글을 파겠다.