Pythonで二分木がヒープ（最大ヒープ）かどうかを判定する方法

この記事では、与えられた二分木がヒープ（最大ヒープ）であるかどうかをPythonで判定するアルゴリズムを解説します。再帰処理を使って「完全二分木であること」と「親子間の大小関係」を効率的にチェックする方法を、実装例とともに見ていきましょう。

ヒープの条件とは？

ある二分木がヒープとみなされるためには、次の2つの性質を満たしている必要があります。

• 完全二分木であること：最後のレベルを除くすべての階層がノードで埋まっている状態になっている
• 最大ヒープの性質を持つこと：すべての親ノードの値が、その子ノードの値以上である

たとえば、次のような木構造が入力として与えられた場合、これらの条件をすべて満たしているため、出力は True になります。

判定アルゴリズムの手順

判定は、次の3つの補助関数を組み合わせて行います。

1. ノード総数を数える（number_of_nodes）

• 引数 root を受け取ります。
• root が null の場合は 0 を返します。
• それ以外の場合は、1 + number_of_nodes(root.left) + number_of_nodes(root.right) を返します（自分自身＋左部分木＋右部分木）。

2. ヒープの性質を確認する（has_heap_property）

• 左右の子がどちらも存在しない（葉ノード）場合は True を返します。
• 右の子だけが存在しない場合は、root.val >= root.left.val が成り立てば True を返します。
• 両方の子が存在する場合は、root.val >= root.left.val かつ root.val >= root.right.val が成り立つときに限り、左右の部分木に対して再帰的に has_heap_property を呼び出した結果を返します。条件を満たさない場合は False を返します。

3. 完全二分木かどうかを確認する（is_complete_tree）

• 引数として root、index、node_count を受け取ります。
• root が null の場合は True を返します。
• index >= node_count の場合は False を返します（ノードが詰め切れていない＝完全二分木ではないことを意味します）。
• それ以外の場合は、左の子をインデックス 2 * index + 1、右の子をインデックス 2 * index + 2 として再帰的に判定した結果の AND を返します。

メイン処理の流れ

1. node_count := number_of_nodes() でノード総数を取得します。
2. is_complete_tree(root, 0, node_count) と has_heap_property(root) がどちらも真であれば True を返します。
3. それ以外の場合は False を返します。

Pythonでの実装例

理解を深めるために、実際のコードを見てみましょう。

class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None
    def number_of_nodes(self, root):
        if root is None:
            return 0
        else:
            return (1 + self.number_of_nodes(root.left) + self.number_of_nodes(root.right))
    def has_heap_property(self, root):
        if (root.left is None and root.right is None):
            return True
        if root.right is None:
            return root.val >= root.left.val
        else:
            if (root.val >= root.left.val and
                root.val >= root.right.val):
                return (self.has_heap_property(root.left) and self.has_heap_property(root.right))
            else:
                return False
    def is_complete_tree(self, root,index, node_count):
        if root is None:
            return True
        if index >= node_count:
            return False
        return (self.is_complete_tree(root.left, 2 * index + 1, node_count) and self.is_complete_tree(root.right, 2 * index + 2, node_count))
    def is_heap(self):
        node_count = self.number_of_nodes(self)
        if (self.is_complete_tree(self, 0, node_count) and self.has_heap_property(self)):
            return True
        else:
            return False
root = TreeNode(99)
root.left = TreeNode(46)
root.right = TreeNode(39)
root.left.left = TreeNode(14)
root.left.right = TreeNode(5)
root.right.left = TreeNode(9)
root.right.right = TreeNode(33)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(12)
print(root.is_heap())

入力

root = TreeNode(99)
root.left = TreeNode(46)
root.right = TreeNode(39)
root.left.left = TreeNode(14)
root.left.right = TreeNode(5)
root.right.left = TreeNode(9)
root.right.right = TreeNode(33)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(12)

出力

True

まとめ

このように、ノード数のカウント・完全二分木の判定・ヒープ性質の再帰チェックという3つのステップに分解することで、二分木が最大ヒープかどうかを簡潔に判定できます。計算量はいずれも木のノード数 n に対して O(n) となり、実用上も十分な効率です。優先度キューなどのデータ構造を実装する際の基礎知識として、ぜひ押さえておきましょう。