그림 11-2 노드 위 숫자는 배열의 인덱스를 의미합니다. 잘 살펴보면 아주 재미있는 사실을 알 수 있습니다. 부모의 인덱스는 자식 노드를 2로 나눈 값이 됩니다. 예를 들어 키 2의 부모 노드는 인덱스 4를 2로 나눈 인덱스에 있습니다. 키 9를 가진 노드의 인덱스는 3입니다. 이를 2로 나누면 1이 나옵니다. 인덱스 1은 키 9를 가진 노드의 부모입니다. 또 왼쪽 자식 노드의 인덱스는 부모 노드의 인덱스에 2를 곱하면 되고, 오른쪽 자식 노드의 인덱스는 부모 노드의 인덱스에 2를 곱하고 1을 더하면 됩니다.

index(parent) = index(child) / 2

index(left_child) = index(parent) * 2

index(right_child) = index(parent) * 2 + 1

구현에서 중요한 멤버 하나를 더 소개하겠습니다. 힙에 저장된 키 개수를 heapsize 멤버에 담아 둘 것입니다. 배열의 1번 인덱스부터 키가 삽입되기 때문에 heapsize는 키 개수이기도 하지만 힙에 있는 마지막 키의 인덱스이기도 합니다. 힙의 추상 자료형을 기술해 보겠습니다.