[C] Creare un heap albero binario senza l'uso di un array

[Negative_creep]

Ciao a tutti, premetto che non ho mai costruito gli alberi in C e molto probabilmente commetterò diversi errori in quello che voglio esporvi. Guardando la struttura Heap, essa (correggetemi se sbaglio) si basa solitamente su un array di dimensione n nel quale vigono le seguenti regole:

- L'elemento di A[i] >= di quello di A[2i]
- L'elemento di A[i] >= di quello di A[2i+1]
- L'elemento di A[n/2] >= di quello di A[n]

L'operazione che vorrei fare io è quella di ordinare semplicemente un albero in maniera decrescente in modo da avere ad ogni inserimento l'elemento di massima priorità nella radice o, se i figli di dx e sx sono uguali alla radice, averli comunque ad una profondità bassa rispetto all'albero, quindi disponibili subito dopo pochi confronti.
Viste le prestazioni migliori in termini di tempo per la ricerca e l'inserimento di un elemento, ho bisogno di utilizzare come struttura dati l'albero.
Per la creazione di questa struttura dati ho seguito il codice presente a questo indirizzo in fondo alla pagina http://it.wikipedia.org/wiki/Albero_binario mi funziona come albero binario, ma volevo sapere da voi che modifiche potevo apportare per rendere l'albero uno heap senza l'ausilio di un array.

[tuccio`]

se vuoi fare questa cosa immagino tu sappia che lo heap ha qualche proprietà in più

l'array probabilmente è la cosa migliore proprio perché una di queste è che è completo fino al penultimo livello

[Negative_creep]

Il problema è che gli array andrebbero allocati con una certa dimensione, una volta esaurita dovrei riallocare lo stesso spazio in un array grande il doppio e così via...
Vorrei quindi evitare questa cosa, usando un albero come struttura dati e ordinare i nodi in base alla massima priorità, che sarà presente alla radice però non saprei come fare.

[tuccio`]

forse invece di un array potresti usare una matrice "triangolare", in cui ogni riga è un array di dimensione 2^i?

in pratica la situazione rimane simile a quella delll'array, ma ogni volta puoi riallocare solo il vettore delle righe, che è di dimensione logn, cioè l'altezza dello heap, quindi ben più piccolo dell'array usuale

non so se c'è qualcosa di più complicato che ti permette di non riallocare niente, il problema è poter anche accedere a una foglia in O(1)

[Negative_creep]

Ok grazie tuccio! Ci provo...