C++로 최대 힙(Max Heap)에서 최솟값 찾기

문제 정의

이 글에서는 최대 힙(max heap)에 저장된 요소들 중 가장 작은 값을 찾는 방법을 다룹니다.

먼저 아래와 같은 최대 힙을 예로 들어 보겠습니다.

핵심 아이디어

최대 힙에서는 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같습니다. 즉, 어떤 노드든 자식 노드를 가지고 있다면 그 자식 노드의 값이 더 작다는 의미입니다. 따라서 최솟값은 반드시 리프(leaf) 노드 중 하나에 존재합니다.

힙에 n개의 노드가 있다면 리프 노드의 개수는 ceil(n/2)개입니다. 또한 최대 힙은 완전 이진 트리(complete binary tree)이므로 배열로 표현할 수 있으며, 이 경우 첫 번째 리프 노드는 floor(n/2) 인덱스 바로 다음 위치에 나타납니다. 위 예제에서는 첫 번째 리프 노드가 인덱스 5에 해당합니다.

알고리즘

아래 절차를 통해 최대 힙에서 최솟값을 효율적으로 찾을 수 있습니다.

1. 힙에서 첫 번째 리프 노드를 찾아 그 값을 최솟값으로 설정
2. 나머지 모든 리프 노드를 순회하면서 더 작은 값을 가진 리프가 발견되면 최솟값을 갱신

루트부터 내부 노드까지는 탐색할 필요가 없으므로, 전체 노드 n개 중 약 절반인 리프 노드만 확인하면 됩니다. 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 제자리에서 해결할 수 있습니다.

C++ 구현 예제

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int getMinElement(int *heap, int n){
    int minElement = heap[n / 2];
    for (int i = n / 2 + 1; i < n; ++i) {
        minElement = min(minElement, heap[i]);
    }
    return minElement;
}

int main(){
    int heap[] = {120, 90, 100, 70, 75, 80, 60, 25, 40, 35};
    cout << "Min value: " << getMinElement(heap, SIZE(heap)) << "
";
    return 0;
}

실행 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 출력을 얻을 수 있습니다.

Min value: 25

예제 힙 {120, 90, 100, 70, 75, 80, 60, 25, 40, 35}에서 리프 노드는 인덱스 5부터 끝까지인 80, 60, 25, 40, 35입니다. 이 값들 중 가장 작은 25가 결과로 출력됩니다.