[C] coda con priorità con albero binario

[emix0880]

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(array). Tramite visita per livelli (BFS), riempio l' array. 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 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.

[Furla]

la struttura che hai postato corrisponde ad un heap binario.

se sai come funziona un heap, non ti sarà difficile fare un funzione che inserisce all'ultimo posto il nuovo elemento e poi lo fa risalire, specialmente se inserisci nella struttura un puntatore al padre; la cosa importante è poter trovare l'ultimo posto in O(logn).

visto che la struttura della coda è ancora da definire, io userei direttamente un array per implementarla, senza passare per la struttura ad albero.

[emix0880]

Originariamente inviato da Furla

la struttura che hai linkato corrisponde ad un heap binario.

se sai come funziona un heap, non ti sarà difficile fare un funzione che inserisce all'ultimo posto il nuovo elemento e poi lo fa risalire, specialmente se inserisci nella struttura un puntatore al padre; la cosa importante è poter trovare l'ultimo posto in O(logn).

visto che la struttura della coda è ancora da definire, io userei direttamente un array per implementarla, senza passare per la struttura ad albero.

ciao inanzittutto grazie per la risposta. Il mio problema è proprio evitare di usare un array e muovermi direttamente nell' albero. oggi abbiamo trovato la soluzione con delle chiamate ricorsive sui 2 figli per trovare il posto dove inserire e chiamare hepyfy per farlo risalire. abbiamo dovuto agiungere dei controlli per no far continuare la ricorsione una volta che si era trovato il posto dove inserire e averlo fatto risalire.

[Furla]

però immagino che in quel modo controlliate tutti i nodi dell'albero, a quel punto la complessità sarebbe lineare, e non O(logn). se volete trovare l'ultimo posto in O(1) dovrete ingegnarvi usando i puntatori delle foglie per realizzare una lista con inserimento in coda.

[emix0880]

purtroppo non abbiamo una gran libertà implementativa, in quanto questa è una parte del progetto di sistemi operativi e da specifiche non possiamo usare allocazione dinamica, quindi per usare tecniche che usano liste con malloc, dobbiamo farlo con vettori, e il discorso si complia un pò comunque ho quasi finito di scriverla e in teoria dovrebbe funzionare.

[Furla]

non devi allocare nulla più di quello che hai già per fare quello che dico, è solo che uno dei due puntatori delle foglie, invece di essere nullo, contiene l'indirizzo della foglia successiva. in più ovviamente ti serve un puntatore all'ultima foglia per l'inserimento O(1).

[emix0880]

ciao ho provato il tuo metodo è devo dire che è molto valido. Solo che per attuarlo ho aggiunto 3 campi uno al padre, uno al ultimo nodo e uno alla foglia successiva. Man mano che inserisci creo una sorta di lista lungho i livelli dell' albero (tipo addobbo dell' albero di natale ). MA il prof ha detto che se è necessario è meglio non aggiungere campi alla struttura, perchè la rende molto pesante (visto il gran numero di instanze). Allora ha accennato a una modo:

in base a un intero si fa and bit a bit per trovare la posizione da inserire.
es il numero la radice si inserisce quando l' albero è NULL
lo 0 vuol dire sinistra e l' 1 destra
il primo nodo si etichetta con 0 e va a sinistra della radice
il secondo è 1 cioè 1 in binrio quindi destra
il terzo 00 cioè sinistra sinistra
il quarto 01 cioè sinistra destra
ecc ecc

non mi è molto chiaro come implementarlo.
Qualcuno conosce già questo algoritmo?

[qwerty86]

un Heap puoi implementarlo usando un Array, in A[1] c'è la radice, e per ogni elmento i il figlio sinistro si trova nella posizione di indice 2*i e il figlio destro nella posizione 2*i+1.

[Furla]

Originariamente inviato da emix0880

ho aggiunto 3 campi uno al padre, uno al ultimo nodo e uno alla foglia successiva. Man mano che inserisci creo una sorta di lista lungho i livelli dell' albero (tipo addobbo dell' albero di natale ).

in base a un intero si fa and bit a bit per trovare la posizione da inserire.
es il numero la radice si inserisce quando l' albero è NULL
lo 0 vuol dire sinistra e l' 1 destra
il primo nodo si etichetta con 0 e va a sinistra della radice
il secondo è 1 cioè 1 in binrio quindi destra
il terzo 00 cioè sinistra sinistra
il quarto 01 cioè sinistra destra
ecc ecc

non mi è molto chiaro come implementarlo.
Qualcuno conosce già questo algoritmo?

l'albero di natale è il risultato giusto, ma deve essere solo tra il penultimo e l'ultimo livello, e non c'è bisogno di appesantire la struttura: basta usare i puntatori ai figli, e il puntatore al padre dell'elemento puntato ti permetterà di distinguere tra il caso in cui è figlio e quello in cui è in coda, con una condizione del tipo

if(elem->destro->padre==elem) cout<<"destro è figlio di elem";
else cout<<"destro è in coda dopo elem"

non so se ho capito bene come funziona il discorso dell'intero, se ce n'è uno per tutto l'albero e ogni bivio è un bit occhio, perché ti limita a 16 o 32 il livello massimo dell'albero (a seconda della macchina su cui lo compili), penso che sia comunque un numero sufficiente per quello che ci devi fare.
pensandoci bene, in effetti, questo intero potrebbe essere benissimo il numero di elementi dell'albero, a meno del primo bit a 1 a partire da sinistra (che ti consente però di capire dove parte il numero)

[emix0880]

Originariamente inviato da Furla

l'albero di natale è il risultato giusto, ma deve essere solo tra il penultimo e l'ultimo livello, e non c'è bisogno di appesantire la struttura: basta usare i puntatori ai figli, e il puntatore al padre dell'elemento puntato ti permetterà di distinguere tra il caso in cui è figlio e quello in cui è in coda, con una condizione del tipo

if(elem->destro->padre==elem) cout<<"destro è figlio di elem";
else cout<<"destro è in coda dopo elem"

non so se ho capito bene come funziona il discorso dell'intero, se ce n'è uno per tutto l'albero e ogni bivio è un bit occhio, perché ti limita a 16 o 32 il livello massimo dell'albero (a seconda della macchina su cui lo compili), penso che sia comunque un numero sufficiente per quello che ci devi fare.
pensandoci bene, in effetti, questo intero potrebbe essere benissimo il numero di elementi dell'albero, a meno del primo bit a 1 a partire da sinistra (che ti consente però di capire dove parte il numero)

Allla fine sono riuscito a implementare con l' intero in pratica ho creato
static short int p; /* profondità */
static short int n=1; /* numero nodo */

e scendo a seinistra o destra con((n>>p)&1 ==0) e ((n>>p)&1 ==1) e ogni volta che faccio una chiamata ricorsiva faccio p-- e quando ritorna p++ e quando la foglia e quella che satura il livello cio 2^p+1 incremento p++. L' inserimento ora è ok. ora mi serve l' heapify che suppongo non si possa fare button up come per l' array ma sto cercando di farlo dopo che ha inserito ed è risalito alla radice. Applico hepyfi alla radice e ricorsivamente hai figli.

secondo te può andare?

[Furla]

se usi il puntatore al padre puoi fare il posizionamento bottom-up, altrimenti ti tocca farlo ricorsivo partendo dalla radice. puoi evitare di richiamarlo per tutti i nodi, ma per solo quelli che fanno parte del "percorso" memorizzato negli interi.