힙

트리 내의 모든 노드가 부모 노드보다 큰 완전 이진 트리

"힙에서 가장 작은 데이터를 갖는 노드는 뿌리 노드이다."

 

연산은 두 가지 뿐

1. 새 노드 삽입

2. 뿌리 노드를 없애는 최솟값 삭제

 

깊이 n의 노드는 배열의 2^n - 1 ~ 2^n + 1 - 2 요소에 저장

k번 인덱스에 위치한 노드의 양쪽 자식 노드들이 위치한 인덱스

왼쪽 자식 노드 : 2k + 1

오른쪽 자식 노드 : 2k + 2

부모 노드 : (k - 1) / 2