C++で2つのバイナリ最大ヒープ（Max Heap）をマージする方法

問題の概要

配列形式で表された2つのバイナリ最大ヒープ（Max Heap）が与えられたとき、それらを1つの最大ヒープへと統合（マージ）します。

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

アルゴリズム

アプローチは非常にシンプルです。以下の手順で処理を行います。

1. 結果を格納するための新しい配列を作成する
2. 与えられた2つの配列を順番に結果用の配列へコピーする
3. ヒープ構築（Build Heap）を実行し、マージ後の完全な最大ヒープを構成する

ポイントは、2つのヒープをそのまま連結しただけではヒープの性質（親が子以上であること）が保たれないため、最後に必ずヒープを再構築する必要があるという点です。

C++による実装例

以下は、上記のアルゴリズムをC++で実装したサンプルコードです。ヒープ化を行う heapify 関数、ボトムアップ方式でヒープを構築する createMaxHeap 関数、そして2つのヒープを統合する 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);
    }
}
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

計算量について

マージ後の全要素数を N = n1 + n2 とすると、配列へのコピーには O(N)、葉以外のノードから順に heapify を適用するボトムアップ方式のヒープ構築も O(N) で完了します。したがって、本手法の全体計算量は O(n1 + n2) となり、2つのヒープの性質を保ちながら要素を一つずつ挿入していく方法（O(N log N)）よりも効率的です。