바이너리 힙(Binary Heap)의 배열 표현 방법 완벽 정리

힙 순서(heap ordering) 속성을 만족하는 완전 이진 트리(complete binary tree)를 바이너리 힙(binary heap)이라고 합니다.

바이너리 힙은 노드 값의 정렬 기준에 따라 다음과 같이 두 가지 유형으로 나눌 수 있습니다.

바이너리 힙의 두 가지 유형

1. 최소 힙(Min Heap)

각 노드의 값이 부모 노드의 값보다 크거나 같은 힙입니다. 따라서 최소 힙에서는 루트 노드가 항상 전체 트리에서 가장 작은 값을 가집니다.

2. 최대 힙(Max Heap)

각 노드의 값이 부모 노드의 값보다 작거나 같은 힙입니다. 따라서 최대 힙에서는 루트 노드가 항상 전체 트리에서 가장 큰 값을 가집니다.

바이너리 힙의 배열(Array) 표현

바이너리 힙의 값들은 일반적으로 배열 형태로 표현됩니다. 배열로 힙을 나타낼 때 적용되는 기본 규칙은 다음과 같습니다.

• 루트(root) 요소의 인덱스는 0입니다.
• 어떤 노드의 인덱스를 i라고 할 때, 해당 노드와 관련된 노드들의 인덱스는 아래 공식으로 구할 수 있습니다.
  • 왼쪽 자식(Left child) : (2 × i) + 1
  • 오른쪽 자식(Right child) : (2 × i) + 2
  • 부모(Parent) : (i − 1) / 2

위 규칙을 활용하면 힙 구조를 배열로 간단하게 표현할 수 있습니다.

유형별 힙 예제

최소 힙(Min Heap) 예제

루트 노드가 최솟값을 가지며, 모든 자식 노드의 값은 부모 노드의 값보다 큽니다.

배열 표현 :

최대 힙(Max Heap) 예제

루트 노드가 최댓값을 가지며, 모든 자식 노드의 값은 부모 노드의 값보다 작습니다.

배열 표현 :

마무리

바이너리 힙은 우선순위 큐(priority queue), 힙 정렬(heap sort) 등 다양한 알고리즘의 기반이 되는 자료구조입니다. 배열 인덱스 공식만 기억하면 트리 구조를 별도의 포인터 없이 효율적으로 구현할 수 있다는 점이 가장 큰 장점입니다.