[CLRS] [6-1] Heaps (힙)

1. Heaps?

- 우선 힙을 저장하는 자료구조는 배열이다.

- 일반적으로 이진 트리(Binary Tree)로 구현되는 완전 이진 트리의 형태다.

- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

- 구현을 쉽게 하기 위해 0인 인덱스는 사용하지 않고 1부터 사용된다.

- 그림으로 나타내면 다음과 같다. (트리의 높이는 log(n)이 된다.)

 

2. 힙에서의 부모노드와 자식노드의 관계

i번째 노드

- 부모 노드 인덱스 : i//2

- 왼쪽 자식 노드 인덱스 : 2*i

- 오른쪽 자식 노드 인덱스 : 2*i + 1

3. Max Heap

- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 

- 즉, 다음을 만족하는 Heap을 의미한다. 

A[parent(i)] >= A[i]

4. Min Heap

- 부모노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

- 즉, 다음을 만족하는 Heap을 의미한다.

A[parent(i)] =< A[i]