ciao a tutti
il mio problema è questo:

devo scrivere le funzioni che creano una coda con priorità.

la strutura è la seguente:

struct nodo{
int priorità;
nodo dx;
nodo sx;
}

nodo * inserici(nodo **tp, nodo *n) inserisce n nell albero puntato da tp, che ne è la radice.

la mia prima idea è stata di sfruttare l' implementazione con heap(arrey). Tramite visita per livelli (BFS)

riempio l' arrey. Dopo, inserendo l' elemento in ultima posizione, chiamo heapyfi sul suo padre (i/2) per farlo risalire al posto giusto.

Sistemo i puntatori e restituire come radice il puntatore del elemento V[0].

il tutto con complessità O(n)per la visita + O(log n) per le operazioni sull' array.

MA ho scoperto da colleghi che si c' è una soluzione con complessità minore senza creare l' arrey, ma muovendosi sull' albero e facendo chiamate ricorsive sui figli. SU google ho cercato in lungo e il largo ma parlano tutti di heap binari.


Qualcuno mi suggerisce come procedere?

PS. se c' è bisogno si può aggiungere un campo alla struttura per tenere l' indirizzo del padre.