Newsgroup: it.comp.lang.c
Titolo: heap

Come faccio, dato un array non ordinato a creare uno heap ovvero un albero
binario in cui ogni nodo ha valore minore dei suoi figli?
--
----------------------------------------------------------------------------
There are 10 kinds of people in the world:
those who understand binary, and those who don't
----------------------------------------------------------------------------

 binario in cui ogni nodo ha valore minore dei suoi figli?
E' preso da un vecchio codice, spero non ci siano errori nell'originale e/o
di copiatura.
<code>
void insert_heap(int vt[], int ext, int low, int high)
{
    int large = low * 2;
    while (large <= high) {
        if (large < high)
            if (vt[large-1] < vt[large])
                large++;
        if (ext >= vt[large-1])
            break;
        else {
            vt[low-1] = vt[large-1];
            low = large;
            large = low * 2;
        }
    }
    vt[low-1] = ext;
}
int position;
for (position = array_size / 2; position >= 1; position--)
    insert_heap(vt, vt[position-1], position, array_size);
</code>
Una volta che hai ottenuto l'heap, ordinare l'array e' facile: estrai il
primo elemento dell'heap e riaggiorni l'heap con la funzione insert_heap.
-- 
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."

 primo elemento dell'heap e riaggiorni l'heap con la funzione insert_heap.
Scusami, ma non mi sembra di vedere qualche riferimento all'albero, intendo
dire: figlio sx, figlio dx, ecc. La funzione che hai postato lavora solo da
e su un array.

davser wrote:

Nessun riferimento infatti.
L'albero e' solo virtuale e si mappa direttamente sull'array: la radice e'
in posizione 1 (si conta per comodita' la prima come 1), i figli in
posizione 2 e 3, i figli di 2 in posizione 4 e 5, quelli di 3 in 6 e 7...
ovvero data la posizione assoluta partendo da 1, i figli si trovano in
posizione doppia e doppia +1.
Il fatto che mi dica che "lo heap e' un albero binario BLA BLA BLA", non mi
implica che lui voglia veramente un albero binario e che non si accontenti
di averlo mappato sull'array :)
Se vuole un vero heap, c'e' un'implementazione in pseudocodice sul Rivest,
che potrebbe interessare (fa la stessa cosa dell'algoritmo postato, ma nel
caso astratto ed e' piu' facilmente applicabile ad un vero albero).


 caso astratto ed e' piu' facilmente applicabile ad un vero albero).
Cosa e' questo Rivest? Sembra assurdo ma ancora non sono riuscito a trovare
una algoritmo in C (senza pseudocodici) che mi faccia un vero heap...

 scrisse:

Con questa funzione crei un'array "heappizzato", basta ripetere per tutti i
valori dell'array......
void siftup(int array[], int i)
{
int padre;
i++;
if (i > 1)
{
	padre=i/2;
	if (array[--padre] > array[--i])
	{
		scambia(&array[i],&array[padre]);		
		siftup(array,padre);
	}
}
}


Non lo troverai mai, perché un heap si implementa con un array come già 
ha detto Mox. L'ho studiato nel corso di Algoritmi e Programmazione 
Avanzata all'università.
Quello ke dici tu è un albero, non uno heap.
Se implementassi uno heap con un albero, dovresti avere 2 puntatori da 
aggiungere per ogni elemento, e comporterebbe uno spreco di memoria.
Tanto accedere ai figli non è complicato:
Se heap[LENGHT] è il tuo vettore ke contiene lo heap, allora ci sono due 
casi:
se il tuo heap parte da heap[1]:
- il figlio sinistro di heap[i] = 2*i
- il figlio destro di heap[i] = 2*i + 1
se il tuo heap parte da heap[0]:
- figlio sinistro di heap[i] = 2*i + 1
- figlio destro di heap[i] = 2*i + 2
Io ho sempre scelto il secondo approccio, così non sprechi un elemento 
del vettore.
Se hai ancora dubbi ti mando il codice delle varie funzioni che si fanno 
con gli Heap (principalmente code prioritarie e heapsort) ke ho fatto 
per l'università. Le ho qui sul pc, basta ke chiedi se ti servono.
Spero di essere stato di aiuto.
Ciao!
	Gio

Correggo parte di quello ke ho scritto:
volendo il tuo heap puoi farlo con gli alberi ma ti servono 3 puntatori, 
non 2 come ho detto nel precedente post. Ti serve infatti anche il 
puntatore al padre, perché quando inserisci un nuovo elemento lo metti 
in fondo allo heap, lo confronti col padre e se è maggiore del padre lo 
scambi col padre. Ripeti la cosa finché non trovi il posto giusto 
dell'elemento nello heap.
Se il tuo heap è implementato con un vettore, il padre dell'elemento 
i-esimo è (i-1)/2.
Con gli alberi si può fare, ma sprechi memoria (per i 3 puntatori) ed 
efficienza (codice più complesso). Vedi tu cosa fare! Io ti consiglio di 
farlo con i vettori e se non ci riesci ti invio il file sorgente.
	Gio

davser wrote:

Questo Rivest, e' anche noto come "Cormen, Leiserson, Rivest" -
"Introduzione agli algoritmi", noto sinteticamente come Rivest (che oltre
ad essere il primo dei 3 autori e' la R di RSA tra le altre cose).
Si trovano tutte implementazioni in pseudocodice perche' e' molto piu'
facile ricavare l'algoritmo in qualunque linguaggio di programmazione
partendo dallo pseudocodice, che non partire da un linguaggio di
programmazione e trasformarlo in un'altro.
Ora immagino che "davser" sia un alias di "Davide" o viceversa... prima di
andare a buttarti in una reale implementazione di heap come albero, perche'
l'array non ti basta? Come ho gia' detto, se proprio non puoi farne a meno
ti posto lo pseudocodice generico per gestire l'heap.


	In teoria credo sia possibile implementare uno heap senza spreco di 
puntatori ma bisogna cambiare la logica di utilizzo, e cmq avere un 
codice decisamente più lento e complesso.
	Faccio un'esempio, l'inserimento si fa in testa e si usa la downheap 
(non la upheap).
	DownHeap(nodo *e, nodo **Heap){
		if (e->valore>(*Heap)->valore){
			nodo *tmp=*Heap;
			*Heap=e;
			e=tmp;
			(*Heap)->left=e->left;
			(*Heap)->right=e->right;
			e->right=NULL;									e->left=NULL;
			if ((*Heap)->left==NULL){
				(*Heap)->left=e;
				return;
			}else if ((*Heap)->right==NULL){
				(*Heap)->right=e;
				return;
			}
		}
		if ((*Heap)->right>(*Heap)->left){
			DownHeap(e,&(*Heap)->left);
		}else DownHeap(e,&(*Heap)->right);
	}
	Non sono sicurissimo che funzioni l'ho scritta al volo... cmq la logica 
credo sia questa.
	Resta inteso che per estrarre il valore bisogna seguire una logica 
inversa...
 
 
-- 
Strahd
per stupire mezz'ora basta un libro di storia,
io cercai di imparare la Treccani a memoria... [F.d.A.]

 ti posto lo pseudocodice generico per gestire l'heap.
Non e' tanto per l'aspetto pratico, non mi interessa piu'di tanto realizzare
l'heap da un array in un modo come in un altro. Mi ero prefissato di farlo
come albero vero e proprio e siccome c'ho pensato un pomeriggio intero senza
risultati chiedevo lumi qui.


x Strahd:
Ho già inviato questo codice a davserv ke aveva il problema con lo heap. 
Volevo xò publicarlo per fartelo vedere, Strahd, e così puoi constatare 
ke fatto in questo modo non sprechi i puntatori e il codice è più veloce 
e meno complesso di quello che tu proponi. Magari a te non serve a nulla 
questo codice, ma ho pensato ke ti potesse interessare x curiosità!
In poche righe gestisci l'inserimento nello heap, l'estrazione della 
radice e l'algoritmo di heapsort.
Il programma può essere forse fatto meglio, ma l'idea di fondo da cui 
partire è questa.
Ecco qua:
#include <stdio.h>
#include "heap.h"
static KEY_TYPE A[Nmax];
static int Nelem=-1;
void Heapify(int i,int Nelem)
{
    int l,r,max;
    l=2*i+1;
    r=2*i+2;
    max=(l<=Nelem && A[l]>A[i])? l:i;
    if (r<=Nelem && A[r]>A[max])
       max=r;
    if (max!=i) {
       int swap;
       swap=A[max];
       A[max]=A[i];
       A[i]=swap;
       Heapify(max,Nelem); }
}
void BuildHeap(void)
{
    int i;
    for (i=Nelem/2-1;i>=0;i--)
       Heapify(i,Nelem-1);
}
void Heapsort(void)
{
    int i;
    BuildHeap();
    for (i=Nelem-1;i>0;i--) {
       int swap;
       swap=A[i];
       A[i]=A[0];
       A[0]=swap;
       Heapify(0,i-1); }
}
int HeapInsert(int key)
{
    int i;
    if (Nelem==Nmax)
       return (NULL); /* Coda piena */
    Nelem++;
    i=Nelem;
    while (i>0 && A[(i-1)/2]<key) {
       A[i]=A[(i-1)/2];
       i=(i-1)/2; }
    A[i]=key;
    return (1);
}
int HeapExtract(KEY_TYPE *max)
{
    if (Nelem<0)
       return NULL; /* coda vuota */
    *max=A[0];
    A[0]=A[Nelem--];
    Heapify(0,Nelem);
    return (1);
}

> codice decisamente più lento e complesso.
[...]

Carino l'ho fatto anche io.... scherzi a parte, credo di essermi 
spiegato male, sono d'accordo con te sul fatto che gli heap si 
implementano meglio con array, dicevo solo che è possibile usare anche 
degli alberi binari, a patto di cambiare approccio, in particolare poi 
la funzione che ho scritto non sono neppure sicuro che funzioni (l'ho 
scritta al volo!!!)
l'implementazione che ho fatto e che funziona degli heap è fatta con 
array (e ora mi sto dannando sul radix sort ma questo è un altro 
thread....argh!!!)
