Pages: [1]   Go Down
Print
Author Topic: Piccolo dubbio esercizio  (Read 1102 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
golvellius
Apprendista Forumista
**
Offline Offline

Posts: 124


« on: 23-11-2009, 20:54:36 »

Salve a tutti volevo un chiarimento su un esercizio che mi ha fatto riflettere:

Sia A=[7,X,6,2,1,y,5] un array di interi. Quali delle seguenti coppie di valori per x e y rendono l'array una max heap:

a) 4 , 3
b) 3 , 4
c) Nessuna delle due coppie
d) entrambe le coppie


Allora a prima occhiata mi verrebbe di dire D ovvero entrambe le coppie, ma riflettendo io so che l'heap è una struttura dati che usa un array che possiamo considerare come un albero binario completo solo fino all'ultimo livello , e qui l'array mi da un albero completo  per questo ho considerato come risposta corretta la C ovvero nessuna delle due coppie perchè di base l'array non mi da un heap.

Il ragionamento che sto facendo secondo voi è corretto ?

Grazie per l'attenzione e buona serata.
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #1 on: 26-11-2009, 01:32:16 »

scusa ma perche' l'array dato non e' un heap? o.O
          7
        /    \
       x      6
      / \     / \
     2  1  y   5

come puoi vedere dal disegno l'array e' un max-heap con due incognite ed entrambe le coppie soddisfano la proprieta' del max-heap... testate
Logged
golvellius
Apprendista Forumista
**
Offline Offline

Posts: 124


« Reply #2 on: 26-11-2009, 14:02:05 »

Ciao grazie della risp comunque.

Quando ho postato la domanda non avevo fatto caso a una parte del libro che dopo scrivo:
io avevo capito che l'heap è un albero completo fino al penultimo livello, vedendo che qui mi veniva un albero completo fino all'ultimo livello sono entrato un po in confusione:

Un maxheap io so che è:
                        16
                       /    \
                     14   10
                     / \    /  \
                    8  7  9   3
                   / \  /
                 2  4 1

con l'ultimo livello incompleto in poche parole

nell'esercizio mi ero messo a costruire l'albero dall'array e vedendo che mi veniva un albero completo mi sono incartato.

Qualche giorno dopo ho capito il mio errore da alcune righe del cormen:

Se A[1.....length[A]] contiene numeri validi nessun elemento dopo A[heap-size[A]] dove heap-size[A]<=length[A] è un elemento dell'heap
   
Forse l ho spiegato male ma comunque ho capito adesso, in caso nn è chiaro mi rispiego meglio.

Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #3 on: 17-12-2009, 14:08:02 »

ehi Golvellius, ma dove prendi gli esercizi?!
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Pages: [1]   Go Up
Print
Jump to: