힙은 배열로 구현한다고 했습니다. 트리를 배열로 구현하다니 신기하군요. 이는 완전 이진 트리이기 때문에 가능한 것입니다. 완전 이진 트리의 정의를 기억해 보세요. 트리 높이가 h일 때 h-1 레벨까지는 2^h-1-1의 노드를 가집니다. 레벨에 가능한 모든 노드가 있는 것이지요. 그리고 h 레벨에서는 왼쪽에서 오른쪽으로 노드가 생성됩니다. 이렇게 밀도가 높은 트리이니 배열에 모아 두기 좋습니다. 배열이니 지역성의 원리가 적용되어 캐시 히트의 확률도 그만큼 높아지겠군요.

힙은 배열에서 0번 인덱스를 사용하지 않고 1번 인덱스를 사용합니다(0번 인덱스를 사용하여 구현할 수도 있지만, 일반적으로는 1번 인덱스를 루트로 잡습니다).

그림으로 살펴보겠습니다. 다음 그림은 최대 힙의 키가 배열에 어떻게 삽입되는지 보여 줍니다.

▲ 그림 11-2 최대 힙의 배열 표현