이진 힙(Binary Heap)이란?
이진 힙은 최소 힙(Min Heap) 또는 최대 힙(Max Heap)에 해당하는 완전 이진 트리(Complete Binary Tree)입니다. 최대 힙에서는 루트의 키가 힙에 존재하는 모든 키 중에서 가장 커야 하며, 이 속성은 트리의 모든 노드에 대해 재귀적으로 성립해야 합니다. 최소 힙은 이와 유사하지만, 루트의 키가 항상 가장 작아야 한다는 점이 다릅니다.
이 글에서는 C++를 사용해 최소 힙을 직접 구현하는 방법을 알고리즘, 전체 소스 코드, 실행 결과 순으로 살펴보겠습니다.
알고리즘
min_heap() 함수
min_heap() 함수는 특정 위치의 원소를 자식 노드들과 비교하면서 아래로 내려보내는(sift-down) 방식으로, 해당 서브트리가 최소 힙 속성을 만족하도록 조정합니다.
시작
함수 min_heap(int *a, int m, int n) 선언
정수형 변수 j, t 선언
t = a[m] 으로 초기화
j = 2 * m
while (j <= n) 동안 반복
만약 (j < n && a[j+1] < a[j]) 라면
j = j + 1
만약 (t < a[j]) 라면
break (반복 종료)
그렇지 않고 만약 (t >= a[j]) 라면
a[j / 2] = a[j]
j = 2 * j
a[j/2] = t
return
끝.
build_minheap() 함수
build_minheap() 함수는 마지막 부모 노드(n/2번째)부터 루트까지 역순으로 min_heap()을 호출하여 전체 배열을 최소 힙으로 변환합니다.
시작
함수 build_minheap(int *a, int n) 선언
정수형 변수 k 선언
for (k = n/2; k >= 1; k--)
min_heap(a, k, n) 호출
끝.
C++ 구현 예제
다음은 위 알고리즘을 그대로 구현한 완전한 C++ 프로그램입니다. 사용자로부터 배열의 크기와 원소를 입력받은 후, 최소 힙을 구성하여 결과를 출력합니다.
#include <iostream>
#include <conio.h>
using namespace std;
void min_heap(int *a, int m, int n){
int j, t;
t = a[m];
j = 2 * m;
while (j <= n) {
if (j < n && a[j+1] < a[j])
j = j + 1;
if (t < a[j])
break;
else if (t >= a[j]) {
a[j/2] = a[j];
j = 2 * j;
}
}
a[j/2] = t;
return;
}
void build_minheap(int *a, int n) {
int k;
for (k = n/2; k >= 1; k--) {
min_heap(a, k, n);
}
}
int main() {
int n, i;
cout << "배열의 원소 개수를 입력하세요\n";
cin >> n;
int a[30];
for (i = 1; i <= n; i++) {
cout << "원소 " << (i) << " 입력 : " << endl;
cin >> a[i];
}
build_minheap(a, n);
cout << "최소 힙\n";
for (i = 1; i <= n; i++) {
cout << a[i] << endl;
}
getch();
}
실행 결과
배열의 원소 개수를 입력하세요
5
원소 1 입력 :
7
원소 2 입력 :
6
원소 3 입력 :
2
원소 4 입력 :
1
원소 5 입력 :
4
최소 힙
1
4
2
6
7
동작 원리 요약
입력된 배열 {7, 6, 2, 1, 4}는 build_minheap()을 거치면서 최소 힙 {1, 4, 2, 6, 7}으로 재배열됩니다. 루트(1번 인덱스)의 값이 가장 작은 1이 되었고, 각 부모 노드는 자식 노드보다 작거나 같은 값을 가지므로 최소 힙의 속성이 올바르게 유지된 것을 확인할 수 있습니다.
참고: <conio.h> 헤더와 getch() 함수는 Turbo C++ 등 일부 구형 컴파일러에서만 지원됩니다. Visual Studio나 GCC 같은 현대적인 컴파일러 환경에서는 해당 헤더를 제거하고 getch() 대신 cin.get()을 사용하는 것이 좋습니다.