[C++ 자/알 Note] 힙 이론

이진트리

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

 

이진탐색트리

부모노드를 중심으로 좌측과 우측으로 구분되는 자식들이

부모노드 값보다 작거나(좌측) 큰(우측) 규칙이 유지되는 이진트리를 의미한다

 

이진탐색트리 장, 단점

장점:

- 값의 탐색, 삽입, 삭제 모두 시간복잡도 O(logN)이 평균이다

- 탐색 GOAT이다

단점:

- 트리의 높이 최적화가 안된 불균형 트리인 경우는

시간복잡도가 O(N)이 걸릴 수도 있다

이를 보완하기 위해서 균형이진탐색트리가 등장했다

 

힙트리

부모 노드 값이 항상 자식 노드 값보다

크거나(Max) 작은(Min) 특징을 지닌 트리이다

위의 특징을 위해 노드들이 Swap을 진행하는 과정을 Heapify라고 한다

참고로, 자식 노드들의 좌측 및 우측의 순서는 전혀 상관없다

 

힙트리 구조

데이터가 추가되는 경우

항상 왼쪽 먼저 쌓이는 완전 이진트리이기에

데이터 개수에 따라 트리 구조는 정해져 있다

 

힙트리 구현

힙트리는 배열로 쉽게 구현할 수 있으며

아래의 특징을 지니게 된다

왼쪽 자식은 2 * i 번째

오른쪽 자식은 2 * i + 1 번째 특징을 지니고 있다

부모 노드를 구하는 방법은 i / 2를 하면 구할 수 있다

 

힙트리 삽입

삽입을 하는 경우에는

가장 왼쪽부터 채워나가는 완전이진트리 방식으로

마지막 위치에 값을 먼저 삽입한다

그리고 Heapify를 통해 본인의 위치를 찾고

최종적으로 적절한 자리에 위치한다

 

힙트리 삭제

힙트리에서 삭제는 특정 데이터를 삭제하는 것이 아닌

루트노드만 제거 가능하다

이를 활용해 최소값, 최대값을 추출할 수 있다

 

삭제하는 경우에

루트노드를 삭제하고

해당 위치에 가장 마지막 원소를 배치시킨다

그리고 Heapify를 진행한다

 

힙트리 시간복잡도

- 삽입, 삭제

이미 Hepify가 된 상태에서 진행되기에

올라가거나 내려가면서 왼쪽 혹은 오른쪽과 Swap 하기에 O(logN)이 걸린다

 

- Heapify (전체 배열)

배열 전체를 Heap 구조로 변경하는 경우는 O(N)이 걸린다

 

- Heapify (단일 노드)

단일 노드를 Heap 구조로 변경하는 경우는 O(logN)이 걸린다

 

- 탐색

힙은 정렬되지 않으므로

임의 원소 탐색을 전체 순회를 해야 하며 O(N)이 걸린다