Ricostruire l'Heap

Ci sono due operazioni principali che possono essere eseguite su un Heap: aggiungere un elemento e rimuovere il nodo radice dall’heap.

Dopo ogni operazione, è necessario assicurarsi che le proprietà dell’heap non vengano violate.

Quando si rimuove la radice, si parte dalla cima per arrivare fino alla parte più bassa dell’heap, modificandolo e sistemando la struttura affinché tutti i nodi padre abbiano un valore maggiore dei rispettivi nodi figli (per un max-heap).

Quando si aggiunge un elemento, occorre invece partire dal basso verso l’alto per modificare la struttura e garantire che i nodi padre abbiano valori più grandi dei nodi figli.

Inserire un Nuovo Elemento in un Heap

Per inserire un nuovo valore, prima si aggiunge l’elemento alla fine dell’array, poi si ripristina la proprietà dell’heap scambiando ripetutamente il nuovo elemento inserito con il suo nodo padre, se la proprietà dell’heap non è rispettata:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Heap iniziale
heap.append(6)                        # Aggiungi un nuovo elemento con valore 6

# Salire verso l'alto e ripristinare la proprietà dell'heap
node = len(heap) - 1                  # L'indice del nodo corrente
while node > 1:                       # Finché non abbiamo raggiunto la radice
    parent = node // 2                # Ottieni l'indice del nodo padre
    if heap[node] > heap[parent]:     # Se la struttura dell'heap non è corretta
        heap[node], heap[parent] = heap[parent], heap[node]
    else:                             # Se la struttura è corretta
        break                         # Allora i nodi sovrastanti sono già a posto => fermati
    node //= 2                        # Passa al nodo padre

Eliminare l’Elemento Radice di un Heap

Per eliminare l’elemento radice, lo si sostituisce prima con l’ultimo elemento nell’array, quindi si ripristina la proprietà dell’heap scambiando ripetutamente il nodo con il suo figlio più grande (nel caso di un max-heap) finché il nodo non raggiunge la posizione corretta:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # Heap iniziale
heap[1], heap[-1] = heap[-1], heap[1] # Scambia la radice con l'ultimo elemento
heap.pop()                            # Rimuovi l'ultimo elemento (precedentemente la radice)

# Scendi e ripristina la proprietà dell'heap
node = 1                              # L'indice del nodo corrente
while node < len(heap):               # Finché non abbiamo raggiunto la fine
    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')
    
    # Se la proprietà dell'heap non è violata => fermati qui
    if heap[node] >= left and heap[node] >= right:
        break
    
    # Se left > right => dobbiamo spostarci a sinistra
    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

Sfida: Correggere l’Heap

Dato un min-heap con n numeri, si sa che n-1 di questi numeri rispettano già la proprietà del min-heap. Il n-esimo numero potrebbe invece violare questa proprietà. L’obiettivo è sistemare l’heap affinché tutti i numeri presenti siano conformi alla proprietà del min-heap.

Input

La prima riga dell’input contiene un singolo intero n (1 ≤ n ≤ ).

La riga successiva contiene n numeri interi separati da uno spazio () che rappresentano i valori degli elementi nell’heap.

Output

Il programma deve stampare n interi separati da uno spazio, corrispondenti all’heap corretto.

Esempi

Input (Ingresso)	Output (Uscita)
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

Spiegazione

Esempio 1

Esempio 2