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

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;
}

二分ヒープとは図で学ぶ

二分ヒープの概念についてまとめます。

2分ヒープ(Binary Heap)は、図のように木の各接点に割り当てられたキーが
一つの配列の各要素に対応した完全二分木で表された構造のことです。
下記の図が2分ヒープを表したものです。

                   [1]
                   25

          [2]               [3]
          12                ９

    [4]        [5]    [6]          [7]
     6          8      5            4

 [8]   [9] [10]
  3     2    1

この図を配列で表すと以下のようになります。

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
25  12   9   6   8   5   4   3   2   1

2分ヒープを配列で表す

図では、2分ヒープを1次元配列で表しています。
2分ヒープを表す配列をA、2分ヒープのサイズをHとすると、
A[1,...,H]に2分ヒープの要素が格納されます。

木の添え字を1から、説点の添え字iが与えられた時の各々にアクセスするには

親[i] = floor(i / 2)(床関数)
左の子[i] = 2 * i
右の子[i] (2 * i ) + 1

で表すことができます。

maxヒープとminヒープ

2分ヒープの各説点のキーは、次に上げるヒープの条件を保つように格納されます。

maxヒープ条件
各節点のキーがその親のキー以下

minヒープ条件
節点のキーがその親のキー以上

図であげた2分ヒープはmaxヒープになります
親子関係のみに大小関係があり、兄弟間に制約はありません。

木の巡回とは

木の操作には木の巡回と呼ばれる探索方法があります。
その探索方法を学びます。

例として以下の2分木を定義します。

       0
  1      4
2 3   5 8        
       6 7

この2分木を例として、木の巡回の出力例を見ていきましょう。

木の先行順巡回(Preorder Tree Walk)

根節点、左部分木、右部分木の順で節点の番号を出力します。

出力例
0 1 2 3 4 5 6 7 8

木の中間順巡回(Inorder Tree Walk)

左部分木、根節点、右部分木の順で節点の番号を出力します。

出力例
2 1 3 0 6 5 7 4 8

木の後行順巡回(Postorder Tree Walk)

左部分木、右部分木、根節点の順で節点の番号を出力します。

出力例
2 3 1 6 7 5 8 4 0

では、AIDU ONLINE JUDGEのALDS1_7_Cの木巡回の問題例に、
プログラムをチェックしましょう。

// 先行順巡回
void preParse(int u){
    if(u == NIL)return;
    printf(" %d",u);
    preParse(gNode[u].left);
    preParse(gNode[u].right);
}

// 中間順巡回
void inParse(int u){
    if(u == NIL)return;
    inParse(gNode[u].left);
    printf(" %d",u);
    inParse(gNode[u].right);
}

// 後行順巡回
void postParse(int u){
    if(u == NIL) return;
    postParse(gNode[u].left);
    postParse(gNode[u].right);
    printf(" %d",u);
}

出力する位置を変えることによって、
各々の出力形式で出力しています。

では、全体のソースです。

#include <stdio.h>
#include <iostream>
using namespace std;
// node最大量
#define MAX 100000
#define NIL -1

struct Node {
    int parent;
    int left;
    int right;
};

// 配列で保持する
Node gNode[MAX];

// 先行順巡回
void preParse(int u){
    if(u == NIL)return;
    printf(" %d",u);
    preParse(gNode[u].left);
    preParse(gNode[u].right);
}

// 中間順巡回
void inParse(int u){
    if(u == NIL)return;
    inParse(gNode[u].left);
    printf(" %d",u);
    inParse(gNode[u].right);
}

// 後行順巡回
void postParse(int u){
    if(u == NIL) return;
    postParse(gNode[u].left);
    postParse(gNode[u].right);
    printf(" %d",u);
}

int main(){
    int left,right,v,n,root = 0;
    cin >> n;
    // 初期化
    for(int i = 0;i < n;++i){
        gNode[i].parent = gNode[i].left = gNode[i].right = NIL;
    }
    
    for(int i = 0;i < n;++i){
        cin >> v >> left >> right;
        gNode[v].left = left;
        gNode[v].right = right;
        // 親の設定
        if(left != NIL){
            gNode[left].parent = v;
        }
        if(right != NIL){
            gNode[right].parent = v;
        }
    }

    // rootを探す
    for(int i = 0;i < n;++i){
        if(gNode[i].parent == NIL){
            root = i;
        }
    }
    
    cout << "Preorder\n";
    preParse(root);
    cout << "\n";
    cout << "Inorder\n";
    inParse(root);
    cout << "\n";
    cout << "Postorder\n";
    postParse(root);
    cout << "\n";
    
    return 0;
}