C++로 최대 힙(Max Heap) 구현하기

이진 힙(Binary Heap)은 최소 힙(Min Heap) 또는 최대 힙(Max Heap) 중 하나의 성질을 만족하는 완전 이진 트리(Complete Binary Tree)입니다. 최대 힙에서는 루트 노드의 키 값이 힙에 존재하는 모든 키 값 중에서 가장 커야 하며, 이 성질은 트리의 모든 노드에 대해 재귀적으로 유지되어야 합니다. 최소 힙도 같은 원리이며, 다만 루트가 항상 최솟값이라는 점만 다릅니다.

알고리즘

max_heap 함수

특정 위치 m에서 시작해 해당 서브트리를 최대 힙 성질을 만족하도록 재배치하는 함수입니다.

Begin
    Declare function max_heap()
        Declare j, t of the integer datatype.
        Initialize t = a[m].
        j = 2 * m;
        while (j <= n) do
            if (j < n && a[j+1] > a[j]) then
                j = j + 1
            if (t > a[j]) then
                break
            else if (t <= a[j]) then
                a[j / 2] = a[j]
                j = 2 * j
        a[j/2] = t
        return
End.

build_maxheap 함수

배열 전체를 최대 힙으로 만드는 함수로, 마지막 부모 노드부터 루트까지 역순으로 max_heap을 호출합니다.

Begin
    Declare function build_maxheap(int *a, int n).
        Declare k of the integer datatype.
        for(k = n/2; k >= 1; k--)
            Call function max_heap(a, k, n)
End.

C++ 예제 코드

다음은 사용자로부터 배열 요소를 입력받아 최대 힙을 구성한 뒤 출력하는 완전한 C++ 프로그램입니다.

#include <iostream>
using namespace std;

void max_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_maxheap(int *a, int n) {
    int k;
    for(k = n/2; k >= 1; k--) {
        max_heap(a, k, n);
    }
}

int main() {
    int n, i;
    cout<<"enter no of elements of array\n";
    cin>>n;
    int a[30];
    for (i = 1; i <= n; i++) {
        cout<<"enter elements"<<" "<<(i)<<endl;
        cin>>a[i];
    }
    build_maxheap(a, n);
    cout<<"Max Heap\n";
    for (i = 1; i <= n; i++) {
        cout<<a[i]<<endl;
    }
}

실행 결과

5개의 요소(7, 6, 2, 1, 4)를 입력했을 때의 실행 결과는 다음과 같습니다.

enter no of elements of array
5
enter elements 1
7
enter elements 2
6
enter elements 3
2
enter elements 4
1
enter elements 5
4
Max Heap
7
6
2
1
4

동작 원리 정리

이 코드에서 배열은 인덱스 1부터 사용하며, 인덱스 i의 자식 노드는 각각 2i(왼쪽)와 2i+1(오른쪽)입니다. max_heap 함수는 현재 노드의 값을 임시 변수 t에 저장한 뒤, 두 자식 중 더 큰 값을 골라 아래로 내려가며 적절한 위치를 찾습니다. build_maxheap은 리프 노드가 아닌 마지막 부모(n/2)부터 시작해 루트까지 힙화(heapify)를 수행함으로써 전체 배열을 O(n) 시간에 최대 힙으로 변환합니다.