힙 이론

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

이진 검색 트리 특징

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

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

 

 

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

트리 재배치를 통해 균형을 유지하는 것이 과제

 

 

힙 트리

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

 

1) 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있다.

2) 마지막 레벨에 노드가 있을 떄는, 항상 왼쪽부터 순서대로 채워야 한다.

 

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

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

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

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

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

 

 

 

데이터 추가 시, 

1. 우선 트리 구조를 맞춘다.

위의 그림에서는 6의 오른쪽에 데이터가 생성하게 된다.

2. 생성된 노드의 부모와 비교하여 생선된 노드가 부모보다 크다면 스위칭, 아니다면 고정한다. 이를 연속적으로 실행하여 위치한다.

 

이 알고리즘은 최대값 혹은 최소값을 구현할 때, 가장 효율적인 움직임을 볼 수 있다.

만약 최대값을 추출한다면,

 

1. 가장 상위의 노드를 제거하여 추출한다.

2. 가장 마지막 노드를 제거된 상위 노드에 올려준다.

3. 상위 노드의 2개의 하위 노드를 비교하여 큰 값과 비교를 진행한다.

4. 만약 크다면 고정, 작다면 하위 노드와 상위 노드를 스위칭한다.

5. 이 작업을 반복 실행.

 

이러한, 작업은 시간 복잡도는 logN으로 볼 수 있다.