1. 정의
- 완전 이진 트리로 최소 힙이라면 작은 값이 위쪽에 있고 최대 힙이라면 큰 값이 위쪽에 있다.
- 즉, 최소 힙이라면 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같다.
- 최대 힙이라면 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같다.
2. 특징
- 우선순위큐를 위해 사용되는 자료구조
- 중복된 값을 허용한다
3. 구현
- 배열로 구현한다
- 구현의 용이성을 위해 트리의 인덱스를 1로 시작한다
- 왼쪽 자식의 인덱스 = 부모 인덱스 * 2
- 오른쪽 자식의 인덱스 = 부모 인덱스 * 2 + 1
- 부모의 인덱스 = 자식의 인덱스 / 2
4. 연산
1) 삽입
- 새로운 요소가 들어오면 완전 이진 트리의 맨 뒤에 일단 삽입을 한다
- 삽입한 새로운 노드를 부모와 비교해가면서 최소 힙 혹은 최대 힙에 맞게 교환해 나간다
2) 삭제
- 최대 힙에서는 최대 값을 얻으려고 하는 것이고, 최소 힙에서는 최소 값을 얻으려고 하는 것이니 루트를 삭제하게 된다
- 삭제한 루트 자리에 완전 이진 트리의 맨 뒤에 있던 노드를 집어 넣는다
- 루트와 자식을 비교해 나가면서 최소 힙 혹은 최대 힙 특징을 만족 시키도록 교환해 나간다