Vai al contenuto principale
← OlimpiApp Olimpico

Informatica · Strutture dati

Ordini con un solo scambio sift-up totale, 7 valori

Si considera l'INSIEME di valori $\{6, 9, 1, 7, 3, 10, 4\}$. Tra tutti i $7! = 5040$ possibili ordini di inserimento uno alla volta in un min-heap binario inizialmente vuoto (ogni nuovo valore viene messo nella prima posizione libera dell'array e poi fatto "risalire" scambiandolo col genitore, in posizione $\lfloor (i-1)/2 \rfloor$ per un nodo in posizione $i$, finché il genitore non è più piccolo di lui o si raggiunge la radice), per quanti di essi il numero totale di scambi genitore-figlio è esattamente $1$ (cioè avviene un solo scambio in tutta l'esecuzione, indipendentemente da quando si verifica)?

La tua risposta

Vanno bene sia 3,14 sia 3.14.