[자료구조] 힙 트리(Heap Tree)

heap tree는 배열의 원소를 정렬하기 위한 자료구조이다. 일반적인 트리 구조와는 달리 우선순위에 따라서 빠르게 자료를 검색할 수 있다.

 

 

 

 

특징

 

• heap tree는 최대 힙과 최소 힙으로 구현한다. 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다. 반대로 최소 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리이다.
   
• 완전 이진 트리로 구성되어 있다. 이는 삽입 / 삭제 시 성능을 위해서이다.
  
  
• 중복된 값을 저장할 수 있다. 단순히 최댓값 / 최솟값을 찾아내기 위한 구조이기 때문이다.

 

 

 

 

구현

 heap tree는 완전 이진 트리로 구현되어 배열로 표현할 수 있다.

 

• 루트 노드부터 높이 순서대로 배열에 모두 정렬이 가능하다.
  
  
• 일반적으로 배열의 0번째 인덱스는 사용하지 않고, 첫 번째 인덱스부터 사용한다.
  
  
• 높이 순서대로, 좌에서 우 순서로 배열에 값을 저장한다.
  
  
• 배열의 크기에 따라서 heap tree의 depth가 얼마인지, 부모와 자식 노드의 위치까지 쉽게 검색할 수 있다.

 

 

 

 

데이터 처리 방식

 

• 데이터 검색
  : 최대 힙과 최소 힙의 경우 모두 시간 복잡도는 O(1)이다. heap tree의 특성상 최대 힙일 경우 항상 루트 노드의 값이 가장 큰 값이고 최소 힙일 경우도 마찬가지로 루트 노드의 값이 가장 작기 때문이다.
  
  
• 데이터 삽입
  : 힙에 새로운 요소가 들어오면 새로운 노드를 마지막에 삽입한다. 그리고 새로운 노드와 부모 노드를 우선순위로 비교하여 교환하면서 타고 올라간다.
  
  
• 데이터 삭제
  : 루트 노드의 값을 제거하고 루트 자리에 마지막 노드의 값을 삽입한다. 그리고 올라간 노드의 값과 그 자식 노드들의 값을 비교하면서 부모보다 큰 자식이 있다면(최대 힙) 해당 자식의 값과 교환한다. 만약 두 자식의 값 모두 부모보다 작으면 두 값 중에 큰 값과 위치를 변경한다. 더 이상 큰 값이 없을 때까지 반복한다.