Vai al contenuto principale

Informatica · Strutture dati

Min-heap: due extract-min consecutivi

Un min-heap binario è memorizzato nell'array [2, 5, 3, 9, 6, 8, 4, 10, 12] (posizioni da 1 a 9, radice in posizione 1, figli di i in 2i e 2i+1). L'operazione extract-min rimuove la radice, sposta l'ultimo elemento dell'array in posizione 1 e poi esegue sift-down: il nodo viene scambiato con il minore dei suoi figli (a parità il sinistro) finché entrambi i figli sono maggiori o uguali, o il nodo è una foglia. Dopo due extract-min consecutivi, qual è l'array risultante (posizioni da 1 a 7)?