완전 이진 트리는 새로운 원소를 트리의 마지막 레벨에 추가하는 방식으로 구성할 수 있습니다. 만약 마지막 레벨의 모든 노드가 채워져 있다면 새로운 레벨을 하나 더 만들고, 맨 왼쪽 위치에 노드를 추가합니다. 완전 이진 트리는 트리의 데이터를 배열을 이용하여 저장할 수 있습니다. 즉, 루트 노드를 배열 또는 벡터의 맨 처음에 저장하고, 그다음 레벨의 모든 노드는 왼쪽부터 오른쪽 순서로 저장합니다. 이러한 방식의 완전 이진 트리 표현은 다른 노드를 가리키는 포인터를 저장할 필요가 없기 때문에 메모리 사용 측면에서 효율적입니다. 부모 노드로부터 자식 노드로 이동하는 것은 단순히 배열의 인덱스 계산으로 가능합니다. 만약 부모 노드가 i번째 배열 원소로 저장되어 있다면 자식 노드는 2*i + 1 또는 2*i + 2번째 인덱스로 접근하면 됩니다. 마찬가지로 자식 노드가 i번째 인덱스라면 부모 노드는 (i - 1)/2번째 인덱스입니다. 이러한 공식은 그림 2-14에서 확인할 수 있습니다.

이제 원소를 삽입하거나 삭제할 때 유지해야 할 힙의 불변성(invariants) 또는 조건에 대해 알아보겠습니다. 첫 번째 조건은 최대 원소에 즉각적으로 접근 가능해야 한다는 점입니다. 이를 위해 최대 원소가 항상 고정된 위치에 있어야 합니다. 힙을 구현할 때는 항상 최대 원소가 트리의 루트에 있도록 설정합니다. 이를 위해 부모 노드가 두 자식 노드보다 항상 커야 한다는 불변성을 유지하도록 설정해야 합니다. 이렇게 구성한 힙을 최대 힙(max heap)이라고 합니다.

최대 원소에 빠르게 접근할 수 있다면 반대로 최소 원소에 빠르게 접근할 수 있도록 힙을 구성할 수도 있습니다. 이러한 힙을 만들려면 앞서 설명했던 모든 비교 연산을 반대로 설정하면 됩니다. 이렇게 만들어진 힙을 최소 힙(min heap)이라고 합니다.