Pythonでリストが最大ヒープ（Max Heap）かどうかを判定する方法

数値のリスト nums が与えられたとき、そのリストが最大ヒープ（Max Heap）として成立しているかどうかを判定する問題について解説します。

最大ヒープの条件

リストが最大ヒープであるためには、以下のルールをすべて満たす必要があります。

• インデックス 2*i + 1 が範囲内に存在する場合、nums[i] >= nums[2*i + 1] が成り立つこと
• インデックス 2*i + 2 が範囲内に存在する場合、nums[i] >= nums[2*i + 2] が成り立つこと

つまり、各親ノードの値が、その子ノードの値以上でなければなりません。これはヒープ構造の基本的な性質です。

入力例と出力

たとえば、入力が [5, 3, 4, 1, 2] の場合、出力は True になります。このリストでは、親ノードが常に子ノード以上の値を持っているためです。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• i を 0 から (numsのサイズ) // 2 - 1 まで繰り返します
  • nums[i] >= nums[2*i+1] が成り立たない場合は False を返します
  • i*2+2 <= len(nums)-1 の場合（右の子が存在する場合）、nums[i] >= nums[2*i+2] が成り立たなければ False を返します
• すべてのチェックを通過したら True を返します

ポイントは、葉ノード（子を持たないノード）はチェックする必要がないため、ループ範囲をリストの前半分だけに限定できることです。これにより計算量を抑えられます。

Pythonでの実装例

以下のコードで実際の実装を確認してみましょう。

class Solution:
   def solve(self, nums):
      for i in range(len(nums)//2):
         if not nums[i] >= nums[2*i+1]:
            return False
         if i*2+2 <= len(nums)-1:
            if not nums[i] >= nums[2*i+2]:
               return False
      return True
ob = Solution()
nums = [5, 3, 4, 1, 2]
print(ob.solve(nums))

入力

[5, 3, 4, 1, 2]

出力

True

まとめ

このアルゴリズムの計算量は O(n/2)、つまり O(n) であり、リストの要素数に対して線形時間でヒープ性を検証できます。空のリストや要素が1つのリストの場合も、ループが実行されずに True が返されるため、正しく動作します。ヒープソートや優先度付きキューの実装を理解するうえで、この判定ロジックは非常に有用な基礎知識となります。