Unione di due heap binari perfetti?

Sono stato bloccato su una questione per un po 'e chiedevo se qualcuno mi può puntare nella giusta direzione:Unione di due heap binari perfetti?

Supponiamo cumuli binari vengono rappresentati utilizzando una rappresentazione ad albero puntatore a base invece di un array. Considerare il problema di unire l'heap binario LHS con RHS. Si supponga che entrambi gli heap siano alberi completi completi, contenenti rispettivamente (2^L - 1) e (2^R -1) nodi.
Dare due algoritmi O (log N) per unire i due heap, uno se L = R e uno se | L - R | = 1.

Questo è un problema di compiti a casa, ho solo bisogno di essere indirizzato nella giusta direzione.

fonte

2010-01-22 user220755

L'albero LHS deve essere avviato a sinistra oppure è solo un nome per comodità? – outis

Suggerimento per L = R: far finta di aver rimosso la radice. Fammi sapere se hai bisogno di più.

fonte

2010-01-22 03:03:31 outis

Grazie mille! Lo capisco adesso! – user220755

Questo è un buon suggerimento. Quello che non riesco a capire è, qual è il prof. arrivare a | L-R | = 1? Sembra che l'algoritmo che è il risultato del tuo suggerimento possa funzionare anche in quel caso. – PeterAllenWebb

Pensate alle proprietà di un heap basato su array e in che modo l'algoritmo accennato violerebbe alcune di queste proprietà se | L-R | = 1. In realtà, non si tratta solo di heap basati su array; pensa alla proprietà della forma. – outis

risposta

Problemi correlati