힙(Heap) 자료구조

개요

우선순위 큐를 구현하는 자료구조들을 비교 분석해보면, 균형 이진 검색 트리가 안정적이고 일관된 $O(\log n)$ 성능을 보여준다는 것을 확인했다. 하지만 이진 힙(Binary Heap) 은 특별한 장점을 가진다:

• 검색, 삽입, 삭제: $O(\log n)$ 시간 복잡도
• 최소/최대값 접근: $O(1)$ 시간 복잡도

이러한 특성으로 인해 실시간으로 최우선 순위 원소에 빈번하게 접근해야 하는 시스템에서 널리 활용된다.

힙의 정의와 속성

힙은 완전 이진 트리(Complete Binary Tree) 구조를 기반으로 하며, 다음 두 가지 핵심 속성을 만족해야 한다:

1. 힙 순서 속성 (Heap Order Property)

모든 노드는 자식 노드들과 특정한 순서 관계를 유지해야 한다:

• 최소 힙(Min Heap): 각 노드의 값 ≤ 자식 노드들의 값
• 최대 힙(Max Heap): 각 노드의 값 ≥ 자식 노드들의 값

2. 완전 이진 트리 구조 속성

트리의 높이를 $h$라 할 때, 모든 리프 노드들이 레벨 $h$ 또는 $h-1$에 위치해야 한다. 이는 트리가 완전 이진 트리 형태를 유지함을 의미한다.

배열 기반 구현

힙의 가장 큰 장점 중 하나는 포인터 없이 배열만으로 효율적인 구현이 가능하다는 것이다. 완전 이진 트리의 특성을 활용하여 각 레벨을 순차적으로 배열에 저장한다.

예시 구조

      17
  13        6
1    4   2    5

배열 표현: [17, 13, 6, 1, 4, 2, 5]

인덱스 관계식

노드 인덱스를 $i$라 할 때:

• 부모 노드: $\lfloor\frac{i-1}{2}\rfloor$
• 왼쪽 자식: $2i + 1$
• 오른쪽 자식: $2i + 2$

검증 예시

인덱스 2(값 6)인 노드의 관계:

• 부모: $\lfloor\frac{2-1}{2}\rfloor = 0$ → 노드 17 ✓
• 자식들: $2 \times 2 + 1 = 5$, $2 \times 2 + 2 = 6$ → 노드 2, 5 ✓

주요 연산 구현

삭제 연산 (Extract-Min/Max)

Percolate Down(흘러내리기) 알고리즘을 사용한다:

1. 루트 노드(최우선순위 원소) 제거
2. 마지막 리프 노드를 루트 위치로 이동
3. 힙 속성 복원을 위해 percolate down 수행:
   • 현재 노드와 자식 노드들 비교
   • 힙 조건에 위배되면 적절한 자식과 교환
   • 조건을 만족하거나 리프에 도달할 때까지 반복

시간 복잡도: $O(\log n)$

삽입 연산 (Insert)

반대로 Percolate Up 알고리즘을 사용한다:

1. 새 원소를 마지막 위치(완전 이진 트리 유지)에 삽입
2. 힙 속성 복원을 위해 percolate up 수행:
   • 현재 노드와 부모 노드 비교
   • 힙 조건에 위배되면 부모와 교환
   • 조건을 만족하거나 루트에 도달할 때까지 반복

시간 복잡도: $O(\log n)$

성능 분석

| 연산 | 시간 복잡도 | 설명 |
| --------- | ----------- | ------------ |
| 최소/최대값 조회 | $O(1)$ | 루트 노드 직접 접근 |
| 삽입 | $O(\log n)$ | 상향 침투 과정 |
| 삭제 | $O(\log n)$ | 하향 침투 과정 |
| 힙 생성 | $O(n)$ | Bottom-up 힙화 |

이러한 특성으로 인해 힙은 우선순위 큐, 힙 정렬, 그래프 알고리즘의 핵심 자료구조로 활용되고 있다.