class Prio():
    """
    On utilise un tas classique mais, pour chaque sommet du graphe,
    on se souvient de l'(unique) position à ce noeud apparait dans le tas.
    Éléments du tas : (priorité, noeud)
    """
    
    
    def __init__(self, n, verbose=False):
        """ `n` : nombre de sommets dans le graphe """
        self.tas = []
        self.position = [None]*n
        self.verbose = verbose
    
    def distance(self, noeud):
        if self.position[noeud] is None:
            return float('inf')
        return self.tas[self.position[noeud]][0]
    
    def echange(self, i, j):
        noeud_i, noeud_j = self.tas[i][1], self.tas[j][1]
        self.tas[i], self.tas[j] = self.tas[j], self.tas[i]
        self.position[noeud_i], self.position[noeud_j] = self.position[noeud_j], self.position[noeud_i]

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

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

    def mise_a_jour(self, poids, noeud):
        if self.verbose: print("Mise à jour du noeud {}. Poids : {}".format(noeud, poids))
        if poids > self.distance(noeud):
            if self.verbose: print("Nouveau poids : trop grand.")
            return
        elif self.position[noeud] is None:
            if self.verbose: print("Ajout du noeud.")
            self.tas.append((poids, noeud))
            pos = len(self.tas)-1
            self.position[noeud] = pos
            self.percolation_up( pos)
        else:
            if self.verbose: print("Mise à jour : diminution du poids.")
            pos = self.position[noeud]
            self.tas[pos] = (poids, noeud)
            self.percolation_up(pos)
            self.percolation_down(pos)
        
    def heappop(self):
        if len(self.tas)==0: return
        echange(0, len(self.tas)-1)
        mini = self.tas.pop()
        self.percolation_down(0)
        return mini
    
    def _repr_svg_(self):
        """ Permet d'afficher le graphe dans Jupyter """
        import graphviz
        if self.verbose:
            print("Positions :", self.position)
            print("Tas : ", self.tas)
        n, inf = len(self.tas), float('inf')
        s = ["digraph TasMin {", "node[shape=rectangle]"]
        for i in range(n):
            s.append('{} [label="{}"]'.format(i, self.tas[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')._repr_svg_()

p = Prio(10, verbose=True)

import random
noeud, poids = random.randint(0, 9), random.randint(0, 999)
p.mise_a_jour(poids, noeud)
p

Mise à jour du noeud 2. Poids : 698
Ajout du noeud.
Positions : [None, 1, 4, None, None, 3, None, 2, None, 0]
Tas :  [(85, 9), (418, 1), (773, 7), (855, 5), (698, 2)]