salve ragazzi, studio informatica all'università e mi sono trovato di fronte a questi esercizi di algoritmica sugli heap...ora il punto 1 sono riuscito a farlo da solo, per i punti 2 e 3 avrei bisogno di una piccola mano, almeno per capire l'intuizione che sta dietro alla soluzione. In particolare per il punto 3 avevo pensato di costruire un heap di minimo di k elementi e quindi costo Teta(k) e poi di fare k volte la procedura "Extract_min"(che preso un heap di minimo mi estrae e restituisce il minimo e ripristina la proprietà di heap di minimo) con costo O(klog(k)). Ma non risulta come il costo richiesto dall'esercizio(anche se forse più efficiente).
algo1.JPG
P.S. chiedo scusa in anticipo se forse ho sbagliato sezione, ma non ne ho trovato una più adatta.