Heap Tree

Heap tree의 정의

heap tree는 트리 구조로 구현된 자료구조이다. 일반적인 트리 구조와는 다르게, heap tree는 우선순위에 따라서 빠르게 자료를 검색할 수 있는 구조이다.

Heap tree의 구조

heap tree는 느슨한 정렬 구조로 구현되어 있다.
부모 노드의 값은 자식 노드의 값보다 항상 크거나 항상 작게 정렬되어 있다. 그렇지만 자식 노드끼리의 값의 크기에 따라 좌우 위치는 정렬하지 않는다.

Heap tree의 특징

1. 완전 이진 트리
   완전 이진 트리로 구성되어 있다. 단순히 최댓값, 최솟값을 찾기 위해서는 완전 이진 트리로 구성할 필요는 없지만, 삽입/삭제 시 성능을 위해 완전 이진 트리로 구현하게 된다.
2. 중복된 값 저장
   일반적인 이진 탐색 트리와 다르게 중복된 값을 저장할 수 있다. 단순히 최댓값/최솟값을 찾아내기 위한 구조이기 때문
3. 최대 힙/최소 힙
   루트 노드에 가장 큰 값이 위치하며 자식 노드로 내려갈수록 작은 값이 위치하게 구현한다면 최대 힙
   루트 노드에 가장 작은 값이 위치하며 자식 노드로 내려갈수록 큰 값이 위치하게 구현한다면 최소 힙

Heap tree의 데이터 처리 방식

1. 데이터 검색(최대값/최소값)
   최대 힙일 경우 최댓값을 찾는데 걸리는 시간복잡도는 O(1). heap tree의 특성상 최대 힙일 경우 항상 루트 노드의 값이 가장 큰 값이기 때문에 최댓값은 항상 루트 노드의 값을 불러오기만 하면 된다.
2. 데이터 삽입
   1. 가장 마지막 노드에 새로운 값을 저장한다.
   2. 삽입된 노드의 값과 부모 녿의 값을 비교한다.
   3. 최대 힙일 경우, 부모의 값이 더 크다면 부모의 값과 위치를 서로 변경한다.
   4. 더 이상 위치가 바뀌지 않을 때까지 1~3까지의 과정을 반복한다.
3. 데이터 삭제
   1. 루트 노드의 값을 제거한다.
   2. 루트 자리에 마지막 노드의 값을 삽입한다.
   3. 올라간 노드의 값과 그 자식 노드들의 값과 비교한다.
   4. 부모보다 더 큰 자식이 있다면(최대 힙) 해당 자식의 값과 서로 교환한다. (만약 두 자식의 값이 모두 부모보다 작다면, 두 값과 위치를 변경한다.)
   5. 더 이상 큰 값이 없을 때까지 반복한다.