最大ヒープを出力させるアルゴリズム

ALDS_1_9_B:MaximumHeapを例題にmaxヒープを構築するプログラムを学びます。

最大ヒープとは

以下引用

「節点のキーがその親のキー以下である」という max-ヒープ条件を満たすヒープを、
max-ヒープと呼びます。
max-ヒープでは、最大の要素が根に格納され、ある節点を根とする部分木の節点のキーは、
その部分木の根のキー以下となります。
親子間のみに大小関係があり、兄弟間に制約はないことに注意してください。

この問題でmaxヒープを構築する方法として、2つの関数を用いています。
ひとつは、maxHeapify(A,i)関数で、A[i]をmaxヒープ条件を満たすまで木の葉まで下降させます。

maxHeapify関数

maxHeapify(A,i)はiの左の子と右の子のうち、キーが大きい方を選び、
A[i]よりも大きければ交換する処理を再帰的に繰り返します。
問題に載っている疑似コードをc++に書き直すと以下のようになります。

void maxHeapify(int i){
    int left,right,largest;
    left = 2 * i;
    right = 2 * i + 1;
    
    // 左の子、自分、右の子で値が最大のノードを選択
    if(left <= gSize && gHeap[left] > gHeap[i]){
        largest = left;
    }
    else{
        largest = i;
    }
    // 右の子と比較
    if(right <= gSize && gHeap[right] > gHeap[largest]) largest = right;
    // 値が大きければ交換する
    if(largest != i){
        swap(gHeap[i],gHeap[largest]);
        maxHeapify(largest);
    }
}

buildMapHeap関数

もう一つの関数は、与えられた配列を最大ヒープにするbuildMapHeapです。

この関数では、
子を持つ節点の中で、添え字が最大の節点(2分ヒープの性質上HeapSize / 2となる)から逆順にmaxHeapify(A,i)を行います。

最大ヒープが構築される過程を図で確認する

例として2分ヒープA = {4,1,3,2,16,9,10}
を図にしてみてみましょう。

        4
  1         3
2  16  9  10

子を持つ中で添え字が最大の節点は7 / 2 = 3になりますので、
maxHeapify(A,3)からスタートします。

        4
  1         10
2  16  9    3

続いて、maxHeapify(A,2)関数を呼びます。

        4
  16         10
2  1  9    3

最後に、maxHeapify(A,1)関数を呼びます。

        16
    4        10
2     1   9     3

アルゴリズムに従いmaxヒープが完成しました!

最後に全体のソースコードになります。

#include <iostream>
using namespace std;
#define MAX 2000000

int gHeap[MAX + 1],gSize;

void maxHeapify(int i){
    int left,right,largest;
    left = 2 * i;
    right = 2 * i + 1;
    
    // 左の子、自分、右の子で値が最大のノードを選択
    if(left <= gSize && gHeap[left] > gHeap[i]){
        largest = left;
    }
    else{
        largest = i;
    }
    // 右の子と比較
    if(right <= gSize && gHeap[right] > gHeap[largest]) largest = right;
    
    if(largest != i){
        swap(gHeap[i],gHeap[largest]);
        maxHeapify(largest);
    }
}

int main(){
    cin >> gSize;
    
    for(int i = 1;i <= gSize;++i) cin >> gHeap[i];
    // buildMaxHeap
    for(int i = gSize / 2;i >= 1;--i)maxHeapify(i);
    
    for(int i = 1;i <= gSize;++i){
        cout << " " << gHeap[i];
    }
    cout << endl;
    
    return 0;
}