Vai al contenuto principale

Informatica · Strutture dati

Max-heap in array: sette inserimenti con sift-up

Un max-heap binario è memorizzato in un array con la radice in posizione 1 e i figli del nodo in posizione i nelle posizioni 2i e 2i+1. L'inserimento aggiunge la chiave nella prima posizione libera in fondo e poi esegue sift-up: la chiave viene scambiata con il padre finché il padre è strettamente minore. Partendo da heap vuoto si inseriscono, uno alla volta, 5, 12, 8, 20, 7, 15, 25. Qual è l'array finale (posizioni da 1 a 7)?