Heapify den Heap

Es gibt zwei Hauptoperationen, die auf einem Heap ausgeführt werden können: Wir können ein Element hinzufügen und wir können das Wurzelelement aus dem Heap entfernen.

Nach jeder dieser Operationen müssen wir sicherstellen, dass die Heapeigenschaften nicht verletzt werden.

Beim Entfernen der Wurzel gehen wir von oben nach ganz unten durch den Heap, passen ihn an und korrigieren die Struktur so, dass alle Elternknoten einen größeren Wert haben als ihre Kindknoten (bei einem Max-Heap).

Ein Beispiel für einen Max-Heap mit 8 Knoten

Wenn wir ein Element hinzufügen, gehen wir vom untersten Knoten nach oben und passen die Struktur an, damit die Elternknoten jeweils einen größeren Wert haben als ihre Kindknoten.

Füge ein neues Element in einen Heap ein

Um einen neuen Wert einzufügen, fügen wir den Wert zuerst am Ende des Arrays hinzu. Anschließend wird die Heapeigenschaft wiederhergestellt, indem das neu eingefügte Element wiederholt mit seinem Elternknoten getauscht wird, falls die Heapeigenschaft zwischen Kind und Elternknoten nicht erfüllt ist:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Initialer Heap
heap.append(6)                        # Ein neues Element mit dem Wert 6 hinzufügen

# Nach oben verschieben und die Heapeigenschaft korrigieren
node = len(heap) - 1                  # Index des aktuellen Knotens
while node > 1:                       # Solange wir uns nicht an der Wurzel befinden
    parent = node // 2                # Index des Elternknotens ermitteln
    if heap[node] > heap[parent]:     # Wenn die Heap-Struktur nicht korrekt ist
        heap[node], heap[parent] = heap[parent], heap[node]
    else:                             # Wenn die Struktur korrekt ist
        break                         # Dann stimmen die oberen Ebenen ebenfalls => Abbruch
    node //= 2                        # Zum Elternknoten wechseln

Lösche das Wurzelelement eines Heaps

Um das Wurzelelement zu löschen, wird es zuerst durch das letzte Element im Array ersetzt. Anschließend wird die Heapeigenschaft wiederhergestellt, indem wiederholt der aktuelle Knoten mit seinem größten Kind (bei einem Max-Heap) getauscht wird, bis sich der Knoten an der richtigen Position befindet:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Initialer Heap
heap[1], heap[-1] = heap[-1], heap[1] # Die Wurzel mit dem letzten Element vertauschen
heap.pop()                            # Das letzte Element (ehemals Wurzel) entfernen

# Nach unten gehen und die Heapeigenschaft korrigieren
node = 1                              # Index des aktuellen Knotens
while node < len(heap):               # Solange wir nicht das Ende erreicht haben
    left = heap[2 * node] if 2 * node < len(heap) else float('-inf')
    right = heap[2 * node + 1] if 2 * node + 1 < len(heap) else float('-inf')
    
    # Wenn die Heapeigenschaft nicht verletzt ist => Abbruch
    if heap[node] >= left and heap[node] >= right:
        break
    
    # Wenn left > right => wir gehen nach links
    if left > right:
        heap[2 * node], heap[node] = heap[node], heap[2 * node]
        node = 2 * node
    else:
        heap[2 * node + 1], heap[node] = heap[node], heap[2 * node + 1]
        node = 2 * node + 1

Herausforderung: Den Heap korrigieren

Gegeben ist ein Min-Heap mit n Zahlen, wobei garantiert wird, dass n-1 dieser Zahlen bereits die Min-Heap-Eigenschaft erfüllen. Nur die n-te Zahl kann eventuell die Eigenschaft verletzen. Ihre Aufgabe ist es, diesen Heap zu korrigieren, sodass alle Zahlen im Heap tatsächlich die Min-Heap-Eigenschaft erfüllen.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl n (1 ≤ n ≤ ).

Die nächste Zeile enthält n durch Leerzeichen getrennte ganze Zahlen (), die die Werte der Elemente im Heap darstellen.

Ausgabe

Das Programm soll n durch Leerzeichen getrennte ganze Zahlen ausgeben, die den korrigierten Heap repräsentieren.

Beispiele

Eingabe	Ausgabe
7 1 2 5 4 3 6 -3	-3 2 1 4 3 6 5
6 5 6 9 20 10 8	5 6 8 20 10 9

Erklärung

Beispiel 1

Beispiel 2