힙(heap)은 내부 표현이 동적 배열이며 완전 이진 트리입니다. 힙에는 최대 힙(max heap)과 최소 힙(min heap)이 있습니다. 최대 힙이란 최대 트리이면서 완전 이진 트리라는 의미입니다. 최대 트리(max tree)란 어떤 노드의 키가 자식의 키보다 작지 않은 트리를 의미합니다. 이 절에서는 최대 힙을 구현해 보겠습니다.

다음 그림을 봅시다.

▲ 그림 11-1 최대 힙

그림 11-1을 보면 최대 힙의 두 가지 특성을 확인할 수 있습니다.

1. 어떤 노드의 키가 자식 노드의 키보다 작지 않습니다.

parent.key ≥ child.key

2. 완전 이진 트리입니다.

이 두 가지 특성은 힙의 구현에서 매우 중요하므로 꼭 기억해 두기 바랍니다.