[JAVA] - 힙 (Heap)

힙(Heap)

완전 이진 트리 형태이며, 최솟값 또는 최댓값을 빠르게 찾아내는데 유용한 자료구조이다.

완전 이진 트리는 마지막 레벨을 제외한 모든 노드가 채워져 있어야 하고, 모든 노드들은 왼쪽부터 채워져 있어야 한다.

 

 

 

최소 힙 (Min Heap)

부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태

 

최대 힙 (Max Heap)

부모 노드의 키가 자식 노드의 키보다 크거나 같은 형태

 

 

표준적으로 트리구조는 특정 인덱스에 바로 접근할 수 있는 배열로 구현되고 있다.

일반 배열과는 다르게 시작 인덱스인 root는 0이 아닌 1부터 시작한다.

그리고 각 노드와 대응되는 배열의 인덱스는 변하지 않는다.

 

배열로 구현한 성질

1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2

2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2 + 1

3. 부모 노드 인덱스 = 자식 노드 인덱스 / 2