[C] Info su struttura dati Heap

[Negative_creep]

Ciao a tutti, vi scrivo per avere un'informazione sugli heap. Avrei bisogno di salvare diversi dati in una struttura che mi consenta di poter costruire un albero binario partendo proprio dallo heap.
Tutti gli esempi che ho trovato usano un vettore "heap ordinato" in cui ogni elemento in posizione a[i]>=a[2i] e a[i]>=a[2i+1] da qui quindi è possibile costruire l'albero binario. Però, se ho bisogno di inserire,togliere elementi dinamicamente, il vettore non va bene come struttura di appoggio per l'heap, oppure mi sbaglio?
Anche se creassi un vettore di interi allocato dinamicamente, supponiamo

int* num=(int*)malloc(300*sizeof(int));

come farei a sapere quanti elementi ho all'interno in ogni momento?
Gli esempi sugli heap che ho trovato,usano un vettore che già contiene tutti gli elementi, e poi si procede quindi all'operazione di spostamento dei dati in modo da poterli ordinare correttamente, ma se io ho bisogno di aggiungere dinamicamente dei dati cosa utilizzo? :help:

[Supdario]

La cosa più semplice che puoi fare è sostituire il vettore di int con una struttura che contiene sia il vettore che la quantità di elementi.

Esempio veloce (non testato):

typedef struct {
int *num = NULL;
size_t size = 0;
} vector;

void ridimensiona(vector *x, size_t dimensione)
{
(*x).num = (vector *) realloc((*x).num, sizeof(int) * dimensione);
(*x).size = dimensione;
}

void aggiungi(vector *x, int valore);
{
ridimensiona(&(*x), (*x).size+1);
(*x).num[size-1] = valore;
}

int main()
{
//[...]
vector albero;
aggiungi(&albero, 10);
printf("Il primo elemento è %d e la dimensione è %d", albero.num[0], albero.size);
//[...]
return 0;
}

Questo dovrebbe mostrare "10" e "1", ma non so se funziona.

In ogni caso se hai la possibilità di usare il C++ i std::vector ti alleggerirebbero il lavoro di molto. :asd:

[Negative_creep]

Non posso, devo usare C. Ma se usassi le liste anzichè il vettore?

[goldorak]

Ciao a tutti, vi scrivo per avere un'informazione sugli heap. Avrei bisogno di salvare diversi dati in una struttura che mi consenta di poter costruire un albero binario partendo proprio dallo heap.
Tutti gli esempi che ho trovato usano un vettore "heap ordinato" in cui ogni elemento in posizione a[i]>=a[2i] e a[i]>=a[2i+1] da qui quindi è possibile costruire l'albero binario. Però, se ho bisogno di inserire,togliere elementi dinamicamente, il vettore non va bene come struttura di appoggio per l'heap, oppure mi sbaglio?
Anche se creassi un vettore di interi allocato dinamicamente, supponiamo

int* num=(int*)malloc(300*sizeof(int));

come farei a sapere quanti elementi ho all'interno in ogni momento?
Gli esempi sugli heap che ho trovato,usano un vettore che già contiene tutti gli elementi, e poi si procede quindi all'operazione di spostamento dei dati in modo da poterli ordinare correttamente, ma se io ho bisogno di aggiungere dinamicamente dei dati cosa utilizzo? :help:

Ti serve uno heap binomiale.
Dai un occhiata all'articolo su wikipedia : http://en.wikipedia.org/wiki/Binomial_heap.

[Negative_creep]

Ok grazie, gli darò un'occhiata appena posso. Non sapevo neanche che esistessero! :confused: