Pages: [1]   Go Down
Print
Author Topic: Dubbio domanda min-heap  (Read 698 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« on: 15-09-2010, 17:36:06 »

Abbiamo una heap A di n interi e x un intero. Vogliamo verificare se l'array A' ottenuta dall'array A concatenando l'elemento x in posizione n+1 è una min heap. Qual'è la complessità del miglior algoritmo possibile?

a. O(1)

b. O(log n)

c. O(log^2 n)

d. O(n)

In questa domanda non ho capito se la heap iniziale A è da considerarsi già una min-heap.
Mi chiedo se secondo voi è possibile effettuare tale verifica in tempo O(1) e in tal caso come si può fare!

Grazie
Logged
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #1 on: 15-09-2010, 18:06:07 »

credo di esserci arrivato da solo; ho pensato questo:
se A inizialmente è una min-heap e andiamo a concatenare un intero x, x sarà un foglia; quindi per verificare in tempo O(1) se A' è una min-heap ci basterà controllare se x>A[\lfloor n/2 \rfloor] (il padre di x); se questo è vero allora sarà anche vero che x>A[1] (il minimo contenuto nella radice)

Spero di non aver sbagliato
Logged
8leoncina7
Apprendista Forumista
**
Offline Offline

Posts: 266



« Reply #2 on: 15-09-2010, 21:32:07 »

su una cosa ti posso dare la certezza :-) la risposta è la A e credo che la tua idea sia corretta
 
Logged

meglio fare e pentirsi che non fare e pentirsi lo stesso..
                                                                Machiavelli
Pages: [1]   Go Up
Print
Jump to: