부모 노드의 키가 자식 노드의 키보다 크거나 같은 완전 이진 트리
마지막 레벨 h 외에는 각 레벨 i에 2i-1개의 노드 존재
완전 이진 트리이므로 각 노드에 번호(배열의 인덱스)를 붙일 수 있다.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
9 | 7 | 6 | 5 | 4 | 3 | 2 | 2 | 1 | 3 |
부모 노드와 자식 노드를 찾기가 쉽다.
- 왼쪽 자식의 인덱스 = 부모의 인덱스 * 2
- 오른쪽 자식의 인덱스 = 부모의 인덱스 * 2 + 1
- 부모의 인덱스 = 자식의 인덱스 / 2
최대 힙에서의 삭제
= 가장 큰 키 값을 가진 노드 삭제
= 루트 노드 삭제
삽입/삭제 모두 최악의 경우 트리의 높이에 해당하는 비교 연산 및 이동 연산이 필요하다. O(log n)