C++で最小ヒープを最大ヒープに変換する方法

このチュートリアルでは、最小ヒープ(min heap)を最大ヒープ(max heap)に変換するプログラムについて解説します。

変換対象となる最小ヒープは、配列形式で与えられるものとします。課題は、与えられた最小ヒープをO(n)の時間計算量で最大ヒープへ変換することです。

変換の考え方

最小ヒープを最大ヒープに変換するには、配列の後半(葉に近い内部ノード)から順に「ヒープ化(heapify)」を行います。具体的には、最後の内部ノードであるインデックス(n-2)/2からインデックス0に向かって、各サブツリーが最大ヒープの条件(親が子以上の値を持つ)を満たすように要素を入れ替えていきます。

アルゴリズムの流れ

各ノードについて、左の子(2i+1)と右の子(2i+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)に収まることが知られています。また、元の配列をそのまま書き換えるため追加のメモリは不要で、空間計算量も再帰呼び出しのスタックを除けばO(1)で済みます。