Salve, sto cercando di implementare delle code con priorità tramite heap secondo il procedimento descritto qui, ma, provando l'operazione di dequeue ho qualche problema che non riesco a spiegare; il codice che ho scritto è questo:
codice:
import copy
def pr_ify(j,l,r): 
    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
Ho provato a testarlo con questo codice, 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
codice:
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()
Grazie in anticipo