그림 3-4는 2014년 월드컵 대진표 시합 결과를 트리로 표현한 것이다. 결국 우승한 독일이 루트 노드를 차지한다. 독일은 결승전에서 브라질을 이겼으니 자식 노드는 독일과 브라질이 된다. 부모 노드가 자식 노드를 두 개까지 가질 수 있는 트리를 이진 트리(binary tree)라고 한다. 그림 3-4의 트리는 모든 부모 노드가 자식 노드를 두 개씩 갖고 있으므로 완전 이진 트리(complete binary tree)라고 한다. 트리에서 부모 노드와 자식 노드를 연결하려면 포인터가 필요하다. 완전 이진 트리는 각 레벨에 필요한 노드 개수가 정해져 있으므로 자식 노드를 연결하는 포인터를 사용하지 않아도 배열이나 vector 같은 순차열에 저장할 수 있다. 트리의 각 레벨을 n이라고 한다면 루트 노드는 레벨 0으로 시작하고, 각 레벨에는 2ⁿ개의 노드가 필요하다. 그림 3-4를 보면 월드컵 대진표에 있는 노드를 배열에 어떻게 저장할 수 있는지 알 수 있다. 각 노드 위에 있는 정수가 인덱스 값이다. 루트 노드를 배열에 첫 번째 원소로 저장하고, 이어서 루트의 두 자식 노드를 저장하는 식이다. 두 자식 노드 각각의 자식 노드 쌍이 다음에 오고, 이런 식으로 잎 노드까지 내려간다. 배열에서 인덱스 n에 저장된 노드의 부모 인덱스는 항상 (n-1)/2를 계산한 정숫값이 된다. 배열 원소를 1부터 인덱스를 매긴다면 인덱스 n에 있는 노드의 부모 인덱스를 계산하는 식은 n/2의 정숫값으로 더 간단해진다.

이제 힙을 정의할 수 있다. 힙은 완전 이진 트리이고, 각 노드는 자식 노드에 따라 정렬된다. 부모 노드가 항상 자식 노드보다 크거나 같아야 하는 최대 힙(max heap)이 있고, 부모 노드가 항상 자식 노드보다 작거나 같아야 하는 최소 힙(min heap)이 있다. 부모 노드의 자식 노드끼리는 반드시 정렬되지 않아도 된다.