← OlimpiApp
Medio
Informatica · Strutture dati
Heapify bottom-up per min-heap: array risultante
L'array [21, 9, 15, 3, 12, 7, 5] (posizioni da 1 a 7, radice in posizione 1, figli di i in 2i e 2i+1) viene trasformato in un MIN-heap con la costruzione bottom-up: per i da $\lfloor \frac{7}{2} \rfloor = 3$ fino a 1 si esegue sift-down dal nodo i, scambiando il nodo con il minore dei suoi figli (a parità il sinistro) finché il nodo è minore o uguale a entrambi i figli o è una foglia. Qual è l'array risultante?