Unione di 2 heap

[andra_zx]

Ciao a tutti, ho un problema di dati e algoritmi che mi affligge..XD
Due Heap T1 e T2 devono essere uniti mantenendo le proprietà di heap. Ho pensato che se lo sbilanciamnto fosse al più 1, potrei prendere l' ultimo nodo di un uno dei 2 alberi e utilizzarlo come nuova radice per i 2 alberi. Poi con un down heap bubbling potrei riportare alla normalità la priorità delle chiavi.
Ma il vero problema di pone quando lo sbilanciamento è maggiore di 1..
Qualcuno può ahiutarmi ?

Grazie in anticipo..

P.S. l' algoritmo deve esere complessità O(h1 + h2)

[apatriarca]

Esistono diverse implementazioni di heap (binary, binomial, fibonacci...). Suppongo che tu sia interessato al semplice binary heap e quindi commenterò su quello. Il metodo più semplice e che rispetta la complessità che hai richiesto è quella di costruire un array che contiene i valori dei due heap e poi costruire un heap da questo array (operazione che immagino tu abbia studiato).

[andra_zx]

"apatriarca":Esistono diverse implementazioni di heap (binary, binomial, fibonacci...). Suppongo che tu sia interessato al semplice binary heap e quindi commenterò su quello. Il metodo più semplice e che rispetta la complessità che hai richiesto è quella di costruire un array che contiene i valori dei due heap e poi costruire un heap da questo array (operazione che immagino tu abbia studiato).

Certo ci avevo già pensato, in effetti.. Ma ci sono alcune cose che non mi tornano:
1 - Per portare tutti gli elementi in un array devo fare una visita completa per ogni albero, e questo mi costerà: O(n1 + n2), (n1 e n2 sono il numero dei nodi dei 2 alberi)
2 - Il Bottom up heap per creare un binary heap mi costa O(n), precisamente: O(n1 + n2).

Mentre al massimo mi posso permettere: $O(log(n1) + log(n2))$

[apatriarca]

Non credo sia possibile ottenere una complessità di $O(log(n1) + log(n2))$ con un binary heap per l'operazione di merge.

[andra_zx]

"apatriarca":Non credo sia possibile ottenere una complessità di $O(log(n1) + log(n2))$ con un binary heap per l'operazione di merge.

Eh ma l' esercizio chiede questo..XD comunque tra i suggerimenti c' è scritto di studiare bene i vari passi per bottom up heap.. bè vedrò cosa trovo..

[andra_zx]

comunque nel testo dell' esercizio è scritto: il nuovo albero T conterrà come nodi interni, i nodi dell' unione tra T1 e T2, e deve soddisfare la propietà di heap.
Non l' avevo riportata perchè non ci avevo dato molta importanza, e sinceramente non ne ho neanche capito molto il senso, visto che l' albero T non può avere solo nodi interni, deve per forza averne amnche di esterni. Ma se gli interni sono tutti quelli del' unione di T2 e T1, non restano più nodi da mettere all' esterno..
Però magari questa affermazione può vuol dire qualcosa di implicito..

[apatriarca]

Anche se espressa in modo strano, secondo me la richiesta è semplicemente quella di unire i due heap. Ho cercato un po' e non sono riuscito a trovare implementazioni con quella complessità. In compenso ho trovato questo articolo che può esserti utile

[andra_zx]

"apatriarca":Anche se espressa in modo strano, secondo me la richiesta è semplicemente quella di unire i due heap. Ho cercato un po' e non sono riuscito a trovare implementazioni con quella complessità. In compenso ho trovato questo articolo che può esserti utile

mmh allora mi arrendo..XD