Wie finden Sie eine Eingabe, die eine spezifische Max-Heap-Struktur

Question

Ich verstehe, wie Heaps funktionieren, aber es gibt ein Problem, ich habe keine Ahnung, wie zu lösen.

Angenommen, Sie haben einen max Haufen gegeben sind (kein BST),

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

eine Liste der Eingänge mit denen die gleichen heap Struktur geben würden, so daß jeder aufeinanderfolgende Wert die größte nur irgend möglich sein würde, das wäre:

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

Also mit anderen Worten, wenn Sie wir Wenn Sie zuerst 66, dann 91, dann 10 und dann 107 usw. in einen leeren Max-Heap einfügen, würden Sie mit der gegebenen Heap-Struktur enden, nachdem alles aufgeblüht ist und so weiter. Wie würdest du diesen Input überhaupt finden?

Kann jemand irgendwelche Ideen vorschlagen?

Dank

Answer 1

Betrachten Sie diese max-Heap (die ich als einen Baum zeichnen werde, sondern stellt [7, 6, 5, 4, 3, 1, 2].

7 
6  5 
4 3 1 2 

Was das letzte Element ist, das eingesetzt werden kann? Die in der befüllte letzten Schlitz haufen muss unten rechts im Baum sein, und die bubbling-up-Prozedur kann nur Elemente entlang der Route von diesem Knoten nach oben berührt haben, also muss das vorherige Element 7, 5 oder 2 sein Wenn es 7 war, dann muss der Baum vor dem Einfügen so aussehen (mit _, was den Slot repräsentiert, in den wir gehen) g zum Einfügen vor dem Aufblasen):

5 
6  2 
4 3 1 _ 

, die die Heap-Einschränkung verletzt. Wenn 5 wurde das letzte Element eingefügt wird, dann würde der Haufen so ausgesehen hat:

7 
6  2 
4 3 1 _ 

Dies funktioniert, so könnte 5 gewesen sein das letzte, was eingefügt. Ähnlich könnte 2 auch das letzte eingefügte sein.

Im Allgemeinen könnte ein Element entlang des Pfads zum Knoten ganz rechts unten der letzte Eintrag sein, wenn alle Knoten unterhalb des Pfads mindestens so groß sind wie der andere untergeordnete Knoten des übergeordneten Elements. In unserem Beispiel: 7 kann nicht das letzte Ding sein, da 5 < 6. 5 kann das letzte Ding eingefügt werden, weil 2> 1. 2 kann das letzte Ding eingefügt werden, weil es keine Kinder hat.

Mit dieser Beobachtung kann man alle Input-Sequenzen (in umgekehrter Reihenfolge) generieren, die durch Rekursion zum Heap geführt haben könnten.

Hier ist ein Code, der auf dem von Ihnen angegebenen Beispiel ausgeführt wird und überprüft, dass jede Eingabesequenz, die generiert wird, tatsächlich den angegebenen Heap generiert. Es gibt 226696 verschiedene Eingänge, aber das Programm dauert nur ein paar Sekunden.

# 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