这是正确的吗？最小堆

Question

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

Answer 1

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

第二个级别是可能的，因为 2 和 3 可能是 1 的同级 children。

要达到第三级，3 需要有 2 个用于立即 parent，1 个用于 grandparent，中间没有其他东西。

第四层是不可能的，因为在那里你需要三个小于三的祖先。

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

您可能想通过尝试将 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]

这是正确的吗？最小堆

Is this right? Minheap

algorithm

constraints

permutation

min-heap