Ciao a tutti ho un problema con i binaty heap. Avendi T1 e T2, due heap di altezza h1 e h2, devo unirli in un unico albero T che rispetto ancora la proprietà di heap.
Nel testo dell' esercizio c'è anche la frase: i nodi interni di T sono tutti i nodi dell' unione di T1 e T2. Ciò mi pare strano perchè dico: T non ha nodi esterni ? forse vuol dire qualcosa di implicitò..

Cmq bisogna svolgere tutto in un tempo O(h1 + h2).

Ho pensato di mettere tutti i nodi in una lista, e poi applicare il bottom up heap, ma questo mi costerà O(n)

Se invece lo sbilanciamento dei 2 alberi fosse al più 1, potrei prendere l' ultimo nodo di uno dei 2 alberi e utilizzarlo come nuova radice per i 2 alberi T1 e T2, e poi fare eventualmente un down heap bubbling. Questo rientrerebbe nei tempi richiesti.

Ma se lo sbilanciamento è meggiore di 1 ?

Grazie a tutti in anticipo..