[알고리즘] 힙 트리

힙 트리는 자식 노드가 최대 두개인 이진 트리이다.

힙 트리의 특징은 다음과 같다.

 

1. 부모 노드의 값이 자식 노드 값보다 크다. 

 

2.마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있고(완전 이진 트리) 마지막 레벨의 노드는 왼쪽부터 순서대로 채운다.

그래서 노드 개수를 알면 트리 구조를 확정할 수 있다. 

 

배열을 이용해 힙 구조를 표현할 수 있는데,

i번 노드의 왼쪽 자식은 [2*i + 1] 번 노드,

i번 노드의 오른쪽 자식은 [2*i + 2] 번 노드,

i번 노드의 부모는 [(i - 1)/2] 번 노드

 

3. 새로운 값을 추가할 때는 마지막 레벨에 추가한 후 부모와 도장 깨기를 한다.

도장 깨기란 부모 노드보다 값이 클 경우 부모와 자식을 교체하는 것이다.

 

4. 트리의 최대 값을 꺼내는 것은 루트 노드를 제거하는 것과 같다. 

방법은 먼저 루트 노드를 없애고 마지막 레벨의 끝에 있는 노드를 루트 노드 자리에 위치시킨다.

그리고 역도장깨기로 루트 노드보다 큰 자식 노드와 교체한다. 

 

 

힙 트리는 한 단계씩 내려갈 때마다 반대편에 있는 반 정도의 데이터를 날려버릴 수 있으므로 시간 복잡도 log n 이다.