[A* & Heap] Chapter 02. 힙 이론

우선순위 큐는 힙 트리 구조로 이뤄졌다.

힙트리도 이진트리의 일종이다.

 

- 이진 트리의 개념

각 노드가 최대 두 개의 자식 노드를 가지는 트리

 

 

- 이진 검색 트리 특징

1) 왼쪽을 타고 가면 현재 값보다 작다

2) 오른쪽을 타고 가면 현재 값보다 크다

 

 

- 이진 검색 트리 문제

그냥 무식하게 추가하면, 한쪽으로 기울어져서 균형이 깨진다

트리 재배치를 통해 균형을 유지하는 것이 과제 (AVL, Red-Black)

 

 

- 힙 트리 특징

1. [부모 노드]가 가진 값은 항상 [자식 노드]가 가진 값보다 크다.

2. 노드 개수를 알면, 트리 구조는 무조건 확정할 수 있다.

 

 

- 힙 트리 구현

배열을 이용해서 힙 구조를 바로 표현할 수 있다.

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

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

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