C++ 최소 힙(Min Heap)에서 값 x보다 작은 모든 노드 출력하기

문제 개요

이 문제에서는 하나의 최소 힙(Min Heap)과 값 x가 주어지며, 힙에 속한 노드 중 값이 x보다 작은 모든 노드를 찾아 출력해야 합니다.

최소 힙은 모든 부모 노드의 값이 자식 노드의 값보다 작거나 같은 특수한 형태의 이진 트리입니다. 이러한 성질 덕분에 루트 노드에는 항상 힙 전체에서 가장 작은 값이 위치하게 됩니다.

문제 이해를 위한 예시

다음 예시를 통해 문제를 살펴보겠습니다.

X = 45

출력 − 2 4 7 10 17 22 33 34

접근 방법

이 문제를 해결하는 핵심은 최소 힙 전체를 전위 순회(pre-order traversal)하면서, 주어진 값 X보다 작은 값만 출력하는 것입니다.

• 최소 힙의 성질상 부모 노드의 값은 항상 자식 노드의 값보다 작습니다. 따라서 어떤 노드의 값이 x보다 크거나 같다면, 그 아래에 있는 모든 자식 노드의 값도 반드시 x보다 크거나 같습니다.
• 이를 활용하면 조건을 만족하지 않는 노드를 만난 순간 더 이상 자식 노드를 탐색하지 않고 가지치기(pruning)를 할 수 있어, 불필요한 탐색을 줄여 효율성을 높일 수 있습니다.
• 트리 순회는 재귀(recursion) 함수를 이용해 간단하게 구현할 수 있습니다.

예제 코드

다음 프로그램은 위에서 설명한 해결 방법의 실제 동작을 보여줍니다.

#include <iostream>
using namespace std;
class MinHeap {
    int* harr;
    int capacity;
    int heap_size;
    public:
    MinHeap(int capacity);
    void Heapify(int);
    int parent(int i) { return (i - 1) / 2; }
    int left(int i) { return (2 * i + 1); }
    int right(int i) { return (2 * i + 2); }
    void insert(int k);
    void printSmallerNodes(int k, int pos);
};
void MinHeap::printSmallerNodes(int x, int pos = 0){
    if (pos >= heap_size)
        return;
    if (harr[pos] >= x) {
        return;
    }
    cout<<harr[pos]<<" ";
    printSmallerNodes(x, left(pos));
    printSmallerNodes(x, right(pos));
}
MinHeap::MinHeap(int cap) {
    heap_size = 0;
    capacity = cap;
    harr = new int[cap];
}
void MinHeap::insert(int k) {
    if (heap_size == capacity) {
        cout << "\nOverflow! Size Full\n";
        return;
    }
    heap_size++;
    int i = heap_size - 1;
    harr[i] = k;
    while (i != 0 && harr[parent(i)] > harr[i]) {
        swap(harr[i], harr[parent(i)]);
        i = parent(i);
    }
}
void MinHeap::Heapify(int i) {
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && harr[l] < harr[i])
        smallest = l;
    if (r < heap_size && harr[r] < harr[smallest])
        smallest = r;
    if (smallest != i) {
        swap(harr[i], harr[smallest]);
        Heapify(smallest);
    }
}
int main() {
    MinHeap h(50);
    h.insert(2);
    h.insert(4);
    h.insert(7);
    h.insert(34);
    h.insert(52);
    h.insert(33);
    h.insert(10);
    h.insert(51);
    h.insert(75);
    h.insert(17);
    h.insert(22);
    int x = 45;
    cout<<"All nodes with value smaller than "<<x<<" are\n";
    h.printSmallerNodes(x);
    return 0;
}

실행 결과

All nodes with a value smaller than 45 are 2 4 34 17 22 7 33 10

복잡도 분석

• 시간 복잡도: 최악의 경우 힙의 모든 노드를 방문해야 하므로 O(n)입니다. 다만 가지치기를 통해 x보다 큰 값을 가진 서브트리는 탐색하지 않으므로, 실제로는 전체 노드 수보다 적은 노드만 방문하는 경우가 많습니다.
• 공간 복잡도: 재귀 호출 스택이 트리의 높이에 비례하여 사용되므로 O(log n)입니다.