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:
La tua risposta
Vanno bene sia 3,14 sia 3.14.