이진 힙(Binary Heap)이란?
힙(Heap), 즉 이진 힙(Binary Heap)은 균형 이진 트리(Balanced Binary Tree) 데이터 구조의 특수한 형태로, 완전 이진 트리(Complete Binary Tree) 구조를 따릅니다.
완전 이진 트리에서는 마지막 레벨을 제외한 모든 상위 레벨(l-1 레벨까지)이 노드로 가득 차 있으며, 마지막 레벨(l 레벨)의 노드들은 반드시 왼쪽부터 차례대로 채워집니다.
힙의 핵심 속성
힙에서는 루트 노드의 키(key)가 자식 노드의 키와 비교되어 그에 맞게 배치됩니다. 만약 노드 a가 자식 노드 b를 가진다면, 다음 조건이 반드시 성립해야 합니다.
key(a) ≥ key(b)
부모 노드의 값이 항상 자식 노드의 값보다 크거나 같다는 이 속성이 바로 최대 힙(Max Heap)을 만들어내는 기준입니다.
힙의 두 가지 종류
위 기준에 따라 힙은 크게 두 가지 유형으로 나눌 수 있습니다.
- 최대 힙(Max Heap): 부모 노드의 키가 자식 노드의 키보다 크거나 같은 구조로, 루트 노드에는 항상 전체 데이터 중 최댓값이 위치합니다.
- 최소 힙(Min Heap): 그 반대로 부모 노드의 키가 자식 노드의 키보다 작거나 같은 구조(key(a) ≤ key(b))이며, 루트 노드에는 항상 최솟값이 위치합니다.
다음은 각각 최대 힙과 최소 힙의 대표적인 예시입니다.
참고: 이진 힙의 활용 분야
이진 힙은 우선순위 큐(Priority Queue) 구현, 힙 정렬(Heap Sort), 다익스트라(Dijkstra) 최단 경로 알고리즘 등 컴퓨터 과학 전반에서 널리 활용되는 핵심 자료구조입니다. 삽입과 삭제 연산이 O(log n)의 시간 복잡도로 효율적으로 수행된다는 점이 큰 장점입니다.