[C++] Implementazione Heap con vettori o alberi binari

[ariannaari]

ragazzi...sarò un po' prolissa per spiegarmi bene.
sto studiando le code con priorità epoi di conseguenza alberi e heap. Ora, giunta all'heap, mi si spiega che è un vettore v di dimensione n tale che per ogni i<=n/2 etc...
e che un heap può essere anche visto come un albero binario con al+ l'ultimo livello incompleto in cui la radice contiene il valore max e ogni nodo interno un valore maggiore di quello dei suoi figli. Fin qui tutto chiaro. Poi vengono introdotti i metodi tra cui Insert e DeleteMax di cui vi scrivo l'implementazione che mi viene data:

void insert(heap A, int key, int HeapSize){
HeapSize++;
int z = HeapSize-1;
while (z>0 && A[z/2]<key){
A[z]=A[z/2];
z=z/2;
}
A[z]=key;
}
e l'altra:

int DeleteMax(heap A, int HeapSize){
if (HeapSize>=1){
int max=A[0];
A[0]=A[HeapSize-1];
HeapSize--;
Heapify(A,0,HeapSize);
return max;
}
return -maxint;
}

E dice che entrambi hanno complessità: O(logn)

Ecco la domanda...apparte -maxint che nn capisco cos'è...ma, se mi è appena stata data l'implementazione, perchè mi si chiede di relizzare il seguente esercizio???

Supponete che una coda con priorità sia realizzata tramit uno heap nella forma di albero binario.
-definire lo pseudocodice delle operazioni di insert e deleteMax su tale struttura e valutarne il costo nel caso peggiore

La domanda è: ma perchè mi chiede questo esercizio? non va svolto semplicemente come sopra? oppure si intende prorpio trattarlo come un albero mentre sopra tratta un vettore? E in tal caso...lo pseudocodice comunque sarebbe generico..
cioè..voi come risolvereste l'esercizio??

E poi un altro esercizio:
Definire l'implementazione di una coda con priorità basata sul minimo sottoforma di heap nelle 2 versioni di array e albero binario.

Cos'è una coda con priorità basata sul minimo?
e come si implementa???
Vi prego...aiutatemi!!!

[Cosmy]

io lo heap l'ho sempre visto utilizzare con gli array.. ma certamente puoi realizzarlo come un albero binario, utilizzando il puntatore al padre altrimenti è un casino eseguire le operazioni.
Comunque l'esercizio ti chiede lo PSEUDOcodice, non il codice c.
inoltre quel maxint è chiaramente un refuso.. voleva scrivere max

[ariannaari]

cioè nella definizione diciamo della struttura nodo devo mettere un puntatore al padre? più o meno così?:

struct nodo {
int val;
nodo sin, des, padre;
};

typedef struct nodo * heap;

in questo modo posso accedere al padre del nodo??

riguardo alla seconda domanda sai dirmi qualcosa??

[Cosmy]

intanto ti consiglio di usare Key e non Val.. a livello concettuale è più corretto lavorare su chiavi che non sui valori direttamente. Se fai questo passaggio mentale vedrai che in seguito ti troverai bene a progettare algoritmi.

Un heap può essere banalmente usato per progettare code con priorità basate sul massimo.
Una coda fondamentalmente usa i seguenti metodi:
insert
extract-max
change_key

sono tutte operazioni banali con gli heap eseguite in tempo O(logn).
insert è un inserimento di un processo con una chiave assegnata in coda all'array. Ci fai girare la chamata heapify che lo va a posizionare dove gli compete nell'heap.
Extract tira fuori il massimo e poi risistema la struttura dell'heap (banalmente lo scambi con l'ultimo elemento, esegui heapify su n-1 elementi e ritorni l'elemento estratto)
change key idem.. cambi la chiave di un elemento e poi rifai heapify su quel nodo.
una coda basata sul minimo immagino si faccia con un heap al contrario, invece che max-heap con un min-heap che salva il minimo nella radice

[Cosmy]

scusa... la tua struct è sbagliata.
sin, des e padre sono pointer a nodo. Non nodi
nodo* right,left,dad;

[ariannaari]

Ah ok...ti ringrazio!!!
Ho capito!
Quindi diciamo che il punto cruciale dell'implementazione tramite albero rispetto a quella tramite array sta nell'individuare il nodo a cui diciamo aggangiare il nuovo nodo!
C'è una cosa che non mi è chiarissima negli alberi. A liello di codice, come si accede ad un determinato nodo? Cioè...per accedere alla posizione i del vettore A faccio A[i]...per dire invece "vai su questo nodo nell' Haep come faccio?? So che è una domanda stupida...ma sai aiutarmi??

[Cosmy]

certo.
fai nodo.dad->key

in un topic più sotto però chiedevo un po' di delucidazioni circa l'uso del . rispetto alla ->
Mi è stato detto che sono interscambiabili ma delle differenze di base ci sono.

Comunque gli heap non sono veri e propri alberi e a mio avviso è stupido implementarli con le liste.
Con gli array sai già a priori che la posizione del padre di un nodo è inf(i/2), il figlio sinistro i*2 e quello destro (i*2)+1.
Compatto e immediato, senza puntatori, strutture aggiuntive allocazioni e deallocazioni di memoria (ok ci sarà una memoria massima dell'array.. ma è facile anche gestirla con le eccezioni raddoppiandola tutte le volte che la riempi).

[ariannaari]

infatti...ma che ne so...l'esercizio mi dice così !!! in effetti non ho trovato nessun esempio che usasse le liste! Boh!
cmq grazie mille!
Magari provo a scrivere una versione e te la faccio controllare, così mi dici se può andare! Ancora grazie!

[Cosmy]

volentieri.. visto che ho l'esame tra due giorni e gli heap li devo sapere a menadito.