C++로 최소 힙(Min Heap)에서 최댓값 찾기

문제 정의

최소 힙(minimum heap)이 주어졌을 때, 해당 힙에 포함된 요소 중 최댓값을 찾는 것이 목표입니다.

예시

입력으로 다음과 같은 힙이 주어진다고 가정해 보겠습니다.

이 경우 힙 내 최댓값은 55입니다.

접근 방식 및 알고리즘

• 최소 힙에서는 부모 노드가 항상 자식 노드보다 작거나 같은 값을 가집니다.
• 따라서 자식을 가지는 비단말(내부) 노드는 절대 최댓값이 될 수 없습니다.
• 결국 최댓값은 반드시 단말 노드(leaf node) 중에 존재하므로, 단말 노드들만 순회하며 최댓값을 탐색하면 됩니다.

배열 기반 힙에서 인덱스가 n/2 이상인 요소들은 모두 단말 노드에 해당합니다. 따라서 전체 배열을 순회할 필요 없이 n/2부터 마지막 인덱스까지만 확인하면 되어 시간 복잡도를 O(n/2), 즉 O(n)으로 개선할 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

int getMaxElement(int *heap, int n) {
    // 단말 노드는 n/2 인덱스부터 시작하므로,
    // 해당 범위 내에서만 최댓값을 탐색
    int maxVal = heap[n / 2];
    for (int i = n / 2 + 1; i < n; ++i) {
        maxVal = max(maxVal, heap[i]);
    }
    return maxVal;
}

int main() {
    int heap[] = {15, 27, 22, 35, 29, 55, 48};
    int n = sizeof(heap) / sizeof(heap[0]);
    cout << "Maximum element = " << getMaxElement(heap, n) << endl;
    return 0;
}

실행 결과

Maximum element = 55

정리

최소 힙의 구조적 특성 덕분에 비단말 노드를 검사하지 않고 단말 노드만 확인하는 것만으로 최댓값을 효율적으로 찾을 수 있습니다. 이 방법은 추가적인 메모리 없이 선형 시간 안에 문제를 해결할 수 있는 간단하고 실용적인 접근법입니다.