힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조이다. 힙은 다음과 같은 힙 속성(property)을 만족한다. 즉, A가 B의 부모노드(parent node)이면, A의 키(key)값과 B의 키값 사이에는 일정한 대소관계가 성립한다.
힙에는 두 가지 종류가 있다. 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙(max heap)'이라 하고, 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙(min heap)'이라고 부른다. 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 형제 노드 사이에는 대소관계가 정해지지 않는다.
각 노드의 자식노드 최대 개수는 힙의 종류에 따라 다르지만, 대부분의 경우 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용한다. 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드(root node)에 위치하게 되는 특징이 있으며, 이를 응용하여 우선순위 큐(priority queue)와 같은 추상적 자료형을 구현할 수 있다.
힙의 주요 연산(삽입, 삭제)에 대한 시간 복잡도는 O(log n)이다. 이는 완전이진트리 구조로 인해 힙 트리의 높이가 log₂(n)에 비례하기 때문이다. 힙은 중복된 값을 허용한다는 특징이 있으며, 이는 이진 탐색 트리(binary search tree)와 구별되는 점이다.
힙은 배열을 사용하여 효율적으로 구현할 수 있다. 힙을 배열로 표현할 때, i번째 노드의 왼쪽 자식노드 위치는 2i, 오른쪽 자식노드 위치는 2i+1, 부모노드의 위치는 i/2가 된다. 힙 정렬(heap sort) 알고리즘은 이러한 힙 자료구조를 이용하여 정렬을 수행하는 대표적인 알고리즘이다.
