Tas-Min : implémentation

• Convention : les noeuds sont numérotés à partir de 0 :
• pere = (i-1)//2 ; fils_gauche = 2*i+1 ; fils_droit = 2*i+2

def echange(tas, i, j):
    tas[i], tas[j] = tas[j], tas[i]

def percolation_up(tas, i):
    pere = (i-1)//2
    if i==0 or tas[i] > tas[pere]:
        return
    echange(tas, i, pere)
    percolation_up(tas, pere)

def percolation_down(tas, i):
    n, fg, fd = len(tas), 2*i+1, 2*i+2
    if fd < n and tas[fd] < tas[i] and tas[fd] < tas[fg]:
        echange(tas, i, fd)
        percolation_down(tas, fd)
    elif fg < n and tas[fg] < tas[i]:
        echange(tas, i, fg)
        percolation_down(tas, fg)

def heappush(tas, x):
    tas.append(x)
    percolation_up(tas, len(tas)-1)

def heappop(tas):
    if len(tas)==0: return
    echange(tas, 0, len(tas)-1)
    mini = tas.pop()
    percolation_down(tas, 0)
    return mini

Affichage (graphviz)

Vraiment pas du tout à connaître hein

def tas_to_dot(M):
    import graphviz
    n, inf = len(M), float('inf')
    s = ["digraph TasMin {", "node[shape=rectangle]"]
    for i in range(n):
        s.append('{} [label="{}"]'.format(i, M[i]))
        if 2*i+1 < n:
            s.append("{}->{}".format(i, 2*i+1))
        if 2*i+2 < n:
            s.append("{}->{}".format(i, 2*i+2))
    s.append("}")
    return graphviz.Source('\n'.join(s), engine='dot')

Exemple : Tas-Min

import random
u = []

# évaluer avec `Ctrl-Entrée` pour rester dans la cellule
heappush(u, (random.randint(0, 99)))
print(u)
tas_to_dot(u)

[3, 4, 8, 17, 35, 51, 42, 78, 28, 51, 79, 61, 60, 87, 51, 94, 94, 79, 53, 56]

print(heappop(u), u)
tas_to_dot(u)

3 [4, 17, 8, 28, 35, 51, 42, 78, 53, 51, 79, 61, 60, 87, 51, 94, 94, 79, 56]

Exemple : file de priorité

import random
fileprio = []

distance, sommet = (random.randrange(0, 20), random.choice("ABCD"))
heappush(fileprio, (distance, sommet))
print(fileprio)
tas_to_dot(fileprio)

[(0, 'D'), (1, 'D'), (5, 'A'), (3, 'B'), (3, 'D'), (14, 'C'), (14, 'D'), (13, 'A'), (14, 'C'), (5, 'D'), (17, 'A'), (18, 'C')]