C++에서 최소 힙(Min Heap)을 최대 힙(Max Heap)으로 변환하는 방법

이 글에서는 최소 힙(Min Heap)을 최대 힙(Max Heap)으로 변환하는 프로그램을 C++로 구현하는 방법을 알아보겠습니다.

최소 힙은 배열 형태로 주어지며, 우리의 목표는 이 배열을 O(n) 시간 복잡도 안에서 최대 힙으로 변환하는 것입니다.

접근 방식

최소 힙을 최대 힙으로 변환하는 핵심 아이디어는 간단합니다. 리프 노드가 아닌 마지막 노드부터 루트 노드까지 역순으로 순회하면서 각 서브트리에 대해 힙화(heapify) 작업을 수행하면 됩니다.

배열 기반 힙에서 인덱스 i에 있는 노드의 왼쪽 자식은 2*i+1, 오른쪽 자식은 2*i+2에 위치한다는 점을 활용하여, 부모 노드가 자식 노드보다 크거나 같도록 요소들을 재배치합니다.

예제 코드

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

// 주어진 서브트리를 힙 구조로 변환하는 함수
void convert_arrayheap(int arr[], int i, int n){
    int l = 2*i + 1;   // 왼쪽 자식 인덱스
    int r = 2*i + 2;   // 오른쪽 자식 인덱스
    int largest = i;
    
    if (l < n && arr[l] > arr[i])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
        
    if (largest != i){
        swap(arr[i], arr[largest]);
        convert_arrayheap(arr, largest, n);  // 재귀적으로 하위 트리 정렬
    }
}

// 전체 배열을 최대 힙으로 변환하는 함수
void convert_maxheap(int arr[], int n){
    // 리프가 아닌 모든 노드를 힙화
    for (int i = (n-2)/2; i >= 0; --i)
        convert_arrayheap(arr, i, n);
}

// 배열 출력 함수
void printArray(int* arr, int size){
    for (int i = 0; i < size; ++i)
        printf("%d ", arr[i]);
}

int main(){
    int arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    printf("Min Heap array : ");
    printArray(arr, n);
    
    convert_maxheap(arr, n);
    
    printf("\nMax Heap array : ");
    printArray(arr, n);
    return 0;
}

실행 결과

Min Heap array : 3 5 9 6 8 20 10 12 18 9
Max Heap array : 20 18 10 12 9 9 3 5 6 8

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. 직관적으로는 각 노드마다 O(log n)의 힙화 작업이 수행되어 O(n log n)이라고 생각할 수 있지만, 실제로는 대부분의 노드가 트리의 하위 레벨에 위치하고 그들의 힙화 높이가 짧기 때문에 전체 작업량은 선형 시간에 수렴합니다.

핵심 포인트 정리

• 리프 노드는 자식이 없으므로 이미 유효한 힙이며, 변환이 필요 없습니다.
• (n-2)/2부터 0까지 역순으로 힙화를 수행하면 아래에서 위로 올라가며 힙 속성이 유지됩니다.
• 재귀 호출을 통해 자식과 위치가 바뀐 경우 해당 서브트리도 다시 힙화하여 전체 힙 속성을 보장합니다.