這是正確的嗎？ Minheap

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]