C++로 두 개의 최대 힙(Max Heap) 병합하기

문제 개요

배열 형태로 주어진 두 개의 이진 최대 힙(binary max heap)을 하나의 최대 힙으로 병합하는 것이 목표입니다. 병합된 결과 역시 최대 힙의 성질, 즉 부모 노드가 항상 자식 노드보다 크거나 같은 구조를 유지해야 합니다.

Heap1[] = {20, 17, 15, 10}
Heap2[] = {19, 13, 7}
Result[] = {20, 19, 15, 13, 17, 7, 10}

알고리즘

두 힙을 병합하는 절차는 다음과 같이 단순합니다.

1. 병합 결과를 저장할 새로운 배열을 생성합니다.
2. 주어진 두 배열의 요소를 순서대로 결과 배열에 모두 복사합니다.
3. 병합된 전체 배열에 대해 힙 생성(heapify) 과정을 수행하여 하나의 완전한 최대 힙을 구성합니다.

C++ 구현 예제

아래 코드는 heapify 함수를 재귀적으로 호출해 힙 구조를 만들고, createMaxHeap 함수로 전체 배열을 최대 힙으로 변환한 뒤, mergeMaxHeaps 함수에서 두 힙을 하나로 합치는 과정을 보여줍니다.

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

// 특정 인덱스를 기준으로 서브트리를 최대 힙 형태로 정렬
void heapify(int *arr, int n, int idx){
   if (idx >= n) {
      return;
   }
   int l = 2 * idx + 1;
   int r = 2 * idx + 2;
   int max;
   if (l < n && arr[l] > arr[idx]) {
      max = l;
   } else {
      max = idx;
   }
   if (r < n && arr[r] > arr[max]) {
      max = r;
   }
   if (max != idx) {
      swap(arr[max], arr[idx]);
      heapify(arr, n, max);
   }
}

// 마지막 부모 노드부터 루트까지 heapify를 호출해 최대 힙 생성
void createMaxHeap(int *arr, int n){
   for (int i = n / 2 - 1; i >= 0; --i) {
      heapify(arr, n, i);
   }
}

// 두 힙의 요소를 하나의 배열로 합친 뒤 전체를 다시 최대 힙으로 구성
void mergeMaxHeaps(int *arr1, int n1, int *arr2, int n2, int *result){
   merge(arr1, arr1 + n1, arr2, arr2 + n2, result);
   createMaxHeap(result, n1 + n2);
}

void displayHeap(int *arr, int n){
   for (int i = 0; i < n; ++i) {
     cout << arr[i] << " ";
   }
   cout << endl;
}

int main(){
   int heap1[] = {20, 17, 15, 10};
   int heap2[] = {19, 13, 7};
   int result[SIZE(heap1) + SIZE(heap2)];
   cout << "First max heap: " << endl;
   displayHeap(heap1, SIZE(heap1));
   cout << "Second max heap: " << endl;
   displayHeap(heap2, SIZE(heap2));
   mergeMaxHeaps(heap1, SIZE(heap1), heap2, SIZE(heap2), result);
   cout << "Merged max heap: " << endl;
   displayHeap(result, SIZE(result));
   return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

First max heap:
20 17 15 10
Second max heap:
19 13 7
Merged max heap:
20 19 15 13 17 7 10

정리

이 방식은 두 힙의 요소를 단순히 합친 후 전체 배열에 대해 한 번의 힙 생성 과정을 수행하기 때문에, 시간 복잡도는 O(N + M)입니다(N, M은 각 힙의 크기). 요소 수가 많은 경우에도 효율적으로 동작하며, 병합된 결과는 항상 유효한 최대 힙 구조를 가지게 됩니다.