【Python】リストが最大ヒープを形成しているかどうかを判定する方法

リストがヒープツリー（完全二分木）を表していると仮定します。このとき、その要素が最大ヒープ（max heap）を形成しているかどうかを判定する必要があります。

最大ヒープとは、すべての親ノードがその左右の子ノードのどちらよりも大きい（または等しい）という性質を持つヒープのことです。

たとえば、入力が nums = [8, 6, 4, 2, 0, 3] の場合、出力は True になります。これは、すべての親要素がそれぞれの子要素より大きいためです。

解決手順

この問題は、次の手順で解決できます。

• n := nums のサイズとする
• i を 0 から n - 1 までループする
  • m := i * 2
  • num := nums[i]
  • m + 1 < n の場合：num < nums[m + 1] なら False を返す
  • m + 2 < n の場合：num < nums[m + 2] なら False を返す
• 最後に True を返す

ここで重要なのは、配列形式のヒープでは「インデックス i のノードに対して、左の子は 2i + 1、右の子は 2i + 2 の位置に存在する」という性質です。この性質を利用することで、実際に木構造を構築しなくても、配列を一度走査するだけで判定できます。計算量は O(n) と非常に効率的です。

実装例

以下の実装を見ると、より理解しやすくなります。

def solve(nums):
    n = len(nums)
    for i in range(n):
        m = i * 2
        num = nums[i]
        if m + 1 < n:
            if num < nums[m + 1]:
                return False
        if m + 2 < n:
            if num < nums[m + 2]:
                return False
    return True

nums = [8, 6, 4, 2, 0, 3]
print(solve(nums))

入力

[8, 6, 4, 2, 0, 3]

出力

True