特定の最大ヒープ構造を与える入力を見つける方法

Question

ヒープの仕組みを理解していますが、問題があります。解決方法はわかりません。

のは、あなたが最大ヒープ（ないBST）を与えられているとしましょう

、

[149、130、129、107、122、124、103、66、77、91、98、10、55、 35、72]

あなたの各連続値は、それはおそらくなり得る最大となるように同じヒープ構造与える入力のリスト検索：

[66、91、10、107、 122,35,55,77,130,98,149,124,129,72,103]

つまり、最初に66を挿入してから91を、次に10を107にして空の最大ヒープに挿入すると、すべてのバブリングが終了した後、指定されたヒープ構造になります。どのようにしてこの入力が最初に見つかるでしょうか？

誰にでもアイデアを提案できますか？

おかげ

Answer 1

私はツリーとして描くが、[7, 6, 5, 4, 3, 1, 2]を表します。この最大ヒープを（考えてみましょう。挿入することができます最後の要素を何？で満たされた最後のスロット

7 
6  5 
4 3 1 2 

ヒープはツリーの右下になければならず、バブルアッププロシージャは、そのノードから上へのルートに沿って要素に触れることができるだけであるため、挿入される前の要素は7,5または2でなければなりません。それが7だった場合、木は挿入の前にこれのように見えていたに違いない（_は私たちが行っているスロットを表すバブルアップの前に挿入するグラム）：ヒープの制約に違反

5 
6  2 
4 3 1 _ 

。 5は、最後の要素が挿入されるようにしている場合、ヒープは、このように見えただろう：これは動作します

7 
6  2 
4 3 1 _ 

、その5は、挿入された最後のものだったかもしれません。同様に、2が最後に挿入された可能性もあります。

一般に、パスの下のすべてのノードが少なくともその親の他の子と同じ大きさであれば、一番下のノードへのパスに沿った要素が最後に挿入された可能性があります。この例では、最後に5を挿入することはできません。< 5は2> 1なので最後に挿入することができます。2は挿入されない最後のものです。

このように、再帰によってヒープが発生する可能性のあるすべての入力シーケンスを（逆の順序で）生成することができます。

ここでは、指定した例で実行され、実際に生成される各入力シーケンスが特定のヒープを生成するかどうかを検証するコードを示します。 226696種類の入力がありますが、プログラムの実行には数秒しかかかりません。

# children returns the two children of i. The first 
# is along the path to n. 
# For example: children(1, 4) == 4, 3 
def children(i, n): 
    i += 1 
    n += 1 
    b = 0 
    while n > i: 
     b = n & 1 
     n //= 2 
    return 2 * i + b - 1, 2 * i - b 

# try_remove tries to remove the element i from the heap, on 
# the assumption is what the last thing inserted. 
# It returns a new heap without that element if possible, 
# and otherwise None. 
def try_remove(h, i): 
    h2 = h[:-1] 
    n = len(h) - 1 
    while i < n: 
     c1, c2 = children(i, n) 
     h2[i] = h[c1] 
     if c2 < len(h) and h[c1] < h[c2]: 
      return None 
     i = c1 
    return h2 

# inputs generates all possible input sequences that could have 
# generated the given heap. 
def inputs(h): 
    if len(h) <= 1: 
     yield h 
     return 
    n = len(h) - 1 
    while True: 
     h2 = try_remove(h, n) 
     if h2 is not None: 
      for ins in inputs(h2): 
       yield ins + [h[n]] 
     if n == 0: break 
     n = (n - 1) // 2 

import heapq 

# assert_inputs_give_heap builds a max-heap from the 
# given inputs, and asserts it's equal to cs. 
def assert_inputs_give_heap(ins, cs): 
    # Build a heap from the inputs. 
    # Python heaps are min-heaps, so we negate the items to emulate a max heap. 
    h = [] 
    for i in ins: 
     heapq.heappush(h, -i) 
    h = [-x for x in h] 
    if h != cs: 
     raise AssertionError('%s != %s' % (h, cs)) 

cs = [149, 130, 129, 107, 122, 124, 103, 66, 77, 91, 98, 10, 55, 35, 72] 

for ins in inputs(cs): 
    assert_inputs_give_heap(ins, cs) 
    print ins