[자료구조] 힙(Heap) (feat. 이진 탐색 트리)

힙이란?

: 완전 이진 트리 형태이며, 우선순위 큐를 위해서 만들어진 자료구조

 

완전 이진 트리(complete binary tree)

: 이진 트리 종류 중 하나로, 마지막 level을 제외하고 모든 level이 두 자식 노드로 완전히 채워져 있는 이진 트리

(level - 이진 탐색 트리 게시글의 그림 확인)

 

언제 사용하는가

: 우선순위 큐와 같이 최대/최소값을 빠르게 찾아야하는 자료구조 및 알고리즘 구현에 사용된다. 
EX) java.util.PriorityQueue 

 

사용 이유

: 배열을 통해 최대/최소값 찾으려면 O(N)이 걸리지만, 힙은 O(log N)이 걸린다. (시간복잡도를 줄이기 위해서)

 

힙의 종류

1. 최대 힙 : 부모노드의 값이 자식노드 값보다 크거나 같다 (Root node가 최대값)
2. 최소 힙 : 부모노드의 값이 자식노드 값보다 작거나 같다 (Root node가 최소값)

힙 VS 이진 탐색 트리

공통점 : 둘 다 이진트리
차이점

• 이진 탐색 트리의 노드 값의 크기는 오른쪽 자식 노드 > 부모 노드 > 왼쪽 자식 노드 순이다.
• 힙은 각 노드의 값이 자식노드보다 크거나 같다 또는 작거나 같다.
• 힙은 완전 이진 트리이므로, 무조건 왼쪽 자식 노드부터 데이터를 삽입한다.
• 힙은 데이터의 중복을 허용

이진 탐색 트리는 탐색,

힙은 최대/최소값을 구하기 위한 자료구조.

힙 구현

• 일반적으로 힙은 배열 자료구조를 사용해서 구현한다.
• 구현을 쉽게 하기 위해 배열의 첫번째 index 0은 사용하지 않는다.
  (부모노드를 배열의 index 1로 지정)

부모노드 index = (자식노드 index) / 2
왼쪽 자식노드 index = (부모노드 index) * 2
오른쪽 자식노드 index = (부모노드 index) * 2 + 1

 

 

힙의 시간복잡도

데이터 삽입과 삭제의 경우 연산 자체는 O(1)의 시간 복잡도를 가지지만,
최대 또는 최소힙의 조건이 깨져 노드 위치를 바꾸는 과정이 필요하므로. 최종적으로 O(logN)의 시간 복잡도를 가진다.