algorithm - 这是正确的吗？最小堆

Question

您好，我想知道这些 x 是否位于最小堆的正确位置？我对么？

Answer 1

顶部位置是不可能的，因为 3 会比它的孩子大（下面的某个地方是 1 或 2）。

第二级是可能的，因为 2 和 3 可能是 1 的兄弟姐妹。

要进入第三级，3 需要有 2 表示直系父母，1 表示祖父母，中间没有其他内容。

第四级是不可能的，因为你需要三个小于 3 的 3 的祖先。

列表形式是树形式的直接转换。所以，这也是一场比赛。

您可能想通过尝试将 的每个排列9!插入 minheap 并观察找到 3 的位置来凭经验证明这一点。这是一个执行此操作的 Python 脚本：

from heapq import heapify
from itertools import permutations

has_three = [False] * 9
for t in permutations('123456789'):
    s = list(t)
    heapify(s)
    i = s.index('3')
    has_three[i] = True
print(has_three)

结果是：

[False, True, True, True, True, True, True, False, False]