히프(Heap)는 [ 그림 7-53 ] 과 같이 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해 만든 자료구조이다. 키값이 가장 큰 노드를 찾기 위한 히프를 최대 히프(Max Heap)라 하고, 키값이 가장 작은 노드를 찾기 위한 히프를 최소 히프(Min Heap)라고 한다.

최대 히프는 부모 노드의 키값이 자식 노드의 키값보다 항상 크거나 같은 크기의 관계, 즉 { 부모 노드의 키값 ≥ 자식 노드의 키값 } 의 관계를 가지는 노드들의 완전 이진 트리이다. 그러므로 [ 그림 7-54 ] (a)와 같이 최대 히프에서는 키값이 가장 큰 노드가 루트 노드가 된다. 최소 히프는 부모 노드의 키값이 자식 노드의 키값보다 항상 작거나 같은 크기의 관계, 즉 { 부모 노드의 키값 ≤ 자식 노드의 키값 } 의 관계를 가지는 노드들의 완전 이진 트리이다. 그러므로 [ 그림 7-54 ] 의 (b)와 같이 최소 히프에서는 키값이 가장 작은 노드가 루트 노드가 된다. 히프는 같은 키값의 노드를 중복하여 가질 수 있으며, 일반적으로 말하는 히프는 최대 히프를 말한다.

[ 그림 7-55 ]의 (a)는 완전 이진 트리가 아니기 때문에 히프가 될 수 없고, (b)는 완전 이진 트리지만 부모 노드의 키값과 자식 노드의 키값 사이에 아무런 크기 관계가 없으므로 히프가 될 수 없다.