C++で特定の二分木がヒープかどうかを判定する方法

概念

与えられた二分木に対して、それがヒープの性質(ヒープ属性)を持っているかどうかを検証する必要があります。二分木がヒープであるためには、次の2つの条件を満たしていなければなりません。

• 二分木が完全木であること(最後のレベルを除くすべてのレベルが埋まっている状態)。
• 二分木のすべてのノードの値が、その子ノードの値以上であること(最大ヒープ(max-heap)を想定した場合)。

例

以下の例では、この木はヒープの性質を満たしています。

一方、次の例はヒープの性質を満たしていません。

アプローチ

上記の2つの条件は、それぞれ別々に検証する必要があります。完全性の検証には isComplete(二分木が完全木かどうかをチェックする関数)を、ヒープ性質の検証には isHeapUtil 関数を使用します。

isHeapUtil 関数を実装する際には、以下の点を考慮します。

• 各ノードが持ちうる子の数は、「2つの子」「0個の子(最終レベルのノード)」「1つの子(そのようなノードは最大1つ)」のいずれかです。
• ノードに子が存在しない場合、それは葉ノードなので true を返します(ベースケース)。
• ノードが子を1つだけ持つ場合、それは必ず左の子です(木が完全木であるため)。この場合は、そのノードと唯一の子だけを比較すれば十分です。
• ノードが両方の子を持つ場合は、そのノードにおいてヒープの性質を確認し、左右両方の部分木に対して再帰的に処理を行います。

実装例(C++)

/* C++ program to checks if a binary tree is max heap or not */
#include <bits/stdc++.h>
using namespace std;
struct Node1{
    int key;
    struct Node1 *left;
    struct Node1 *right;
};
struct Node1 *newNode(int k){
    struct Node1 *node1 = new Node1;
    node1->key = k;
    node1->right = node1->left = NULL;
    return node1;
}
unsigned int countNodes(struct Node1* root1){
    if (root1 == NULL)
        return (0);
    return (1 + countNodes(root1->left) + countNodes(root1->right));
}
bool isCompleteUtil (struct Node1* root1, unsigned int index1, unsigned int number_nodes){
    if (root1 == NULL)
        return (true);
    if (index1 >= number_nodes)
        return (false);
    // Recur for left and right subtrees
    return (isCompleteUtil(root1->left, 2*index1 + 1, number_nodes) && isCompleteUtil(root1->right, 2*index1 + 2, number_nodes));
}
bool isHeapUtil(struct Node1* root1){
    if (root1->left == NULL && root1->right == NULL)
        return (true);
    if (root1->right == NULL){
        return (root1->key >= root1->left->key);
    }
    else{
        if (root1->key >= root1->left->key &&
            root1->key >= root1->right->key)
        return ((isHeapUtil(root1->left)) &&
        (isHeapUtil(root1->right)));
        else
            return (false);
    }
}
bool isHeap(struct Node1* root1){
    unsigned int node_count = countNodes(root1);
    unsigned int index1 = 0;
    if (isCompleteUtil(root1, index1, node_count) &&
        isHeapUtil(root1))
    return true;
    return false;
}
// Driver program
int main(){
    struct Node1* root1 = NULL;
    root1 = newNode(10);
    root1->left = newNode(9);
    root1->right = newNode(8);
    root1->left->left = newNode(7);
    root1->left->right = newNode(6);
    root1->right->left = newNode(5);
    root1->right->right = newNode(4);
    root1->left->left->left = newNode(3);
    root1->left->left->right = newNode(2);
    root1->left->right->left = newNode(1);
    if (isHeap(root1))
        cout << "Given binary tree is a Heap\n";
    else
        cout << "Given binary tree is not a Heap\n";
    return 0;
}

出力結果

Given binary tree is a Heap

解説

このプログラムの処理の流れは以下の通りです。

1. countNodes 関数で木全体のノード数を数えます。
2. isCompleteUtil 関数が、各ノードに配列形式のインデックス(根を0として、左の子は 2i+1、右の子は 2i+2)を割り当てながら再帰的に走査し、インデックスがノード総数を超えるノードが存在しないかを確認することで、木の完全性を判定します。
3. isHeapUtil 関数が、各ノードとその子との値の大小関係を再帰的にチェックし、最大ヒープの条件(親の値 ≥ 子の値)が全ノードで成り立つかを検証します。
4. 両方の条件が満たされた場合のみ、isHeap 関数が true を返します。

このアルゴリズムの計算量は、各走査が木の全ノードを一度ずつ訪問するため、O(n) となります(n はノード数)。