Wikipedia:Oracolo: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Code con priorità: nuova sezione |
|||
Riga 501:
--[[Speciale:Contributi/95.245.25.242|95.245.25.242]] ([[User talk:95.245.25.242|msg]])
== Code con priorità ==
Salve, sto cercando di implementare delle code con priorità tramite heap secondo il procedimento descritto [https://docs.google.com/viewer?a=v&q=cache:5zqZkj8jI5wJ:ioi.dsi.unimi.it/heap.pdf+&hl=it&pid=bl&srcid=ADGEESjjEfoZvuPYqmTyT7TvVLd55dccQxf4MIPX05OfE7lbbMEfb-4ix8RAjXpsLddVlq89XfIOWndIBqSRaOZwcGl6ge301JeYsfOW3RsWGYCOwR-5YwX0L0FauuH9QyIaOI2EOC8U&sig=AHIEtbSO7wyiW-xL64EzwSfchXE252bYBA qui], ma, provando l'operazione di dequeue, ho qualche problema che non riesco a spiegarmi; il codice che ho scritto è questo:
<source lang="python">
import copy
def pr_ify(j,l,r): #q[0]=len(q)
tempq,tempp=copy.deepcopy(q[j]),j
while j>l and pr[q[j]]<pr[q[j/2]]: #la priorità dell'i-esimo
#elemento dello heap è minore di quella del padre
q[j]=copy.deepcopy(q[j/2]) #l'elemento che si trovava
#in posizione j viene spostato in posizione j/2
p[q[j]]=j/2 #l'indice nell'array arr dell'elemento che
#occupa nello heap la posizione j è ora quello del padre
j/=2
q[j]=tempq
p[q[j]]=tempp
#credo che il problema sia in questa parte
while j<=r/2:
ch=2*j
if ch<r and pr[q[ch+1]]<pr[q[ch]]:
ch+=1
if pr[q[j]]<=pr[q[ch]]:
break
q[j]=copy.deepcopy(q[ch])
p[q[j]]=ch
j=ch
q[j]=tempq
p[q[j]]=tempp
def pr_ins(j,prj):
q[0]+=1
q[j]=copy.deepcopy(q[0]) #l'elemento aggiunto è l'ultimo dello heap
p[q[0]]=j
pr[j]=prj]
pr_ify(1,q[0],q[0])
def pr_out():
mn=q[1]
if q[0]<=0:
return -1
q[1]=q[q[0]]
q[0]-=1
p[q[1]]=q[0]
pr_ify(1,1,q[0])
return mn
</source>
Ho provato a testarlo con il codice seguente, ma mi risulta che la proprietà per cui [q[p[i]]=i e p[q[j]]=j sia violata e anche l'estrazione del minimo non funzioni; inoltre ho un altro dubbio: perché nell'estrazione del minimo si prende il primo elemento di q e non di p?
<source lang="python">
a=[4,"a","b","c","d"]
pr=[4,3,1,5,0.5] #problemi con l'ultimo
p,q=[0,1,2,3,4],[0,1,2,3,4]
i=1
for x in a[1:]:
pr_ins(i,pr[i])
ii=1
for x in q[1:q[0]+1]:
print ii,p[ii],q[p[ii]],p[q[ii]]
print q[p[ii]]==ii
print p[q[ii]]==ii
ii+=1
i+=1
out=pr_out()
while out!=-1:
out=pr_out()
</source>
--<big>'''䶵'''</big> [[Utente:DostoHouskij|<span style="color:#BB0011">'''Dosto'''</span>]]'''''[[Discussioni utente:DostoHouskij|<span style="color:blue;">Houskij</span>]]''''' <big>'''䶵'''</big> 19:49, 5 mag 2013 (CEST)
| |||