tas.py

class Noeud:
    def __init__(self, key):
        self.key = key
        self.children = []
        self.degree = 0


class TasBinomial:
    def __init__(self):
        self.arbres = []

    def union(self, nouveau_tas):
        self.arbres.extend(nouveau_tas.arbres)
        self.arbres.sort(key=lambda x: x.degree)
        i = 0
        while i < len(self.arbres) - 1:
            if self.arbres[i].degree == self.arbres[i + 1].degree:
                if self.arbres[i].key > self.arbres[i + 1].key:
                    self.arbres[i], self.arbres[i +
                                                1] = self.arbres[i + 1], self.arbres[i]
                self.arbres[i].children.append(self.arbres[i + 1])
                del self.arbres[i + 1]
            else:
                i += 1

    def inserer(self, key):
        nouveau_tas = TasBinomial()
        nouveau_tas.arbres.append(Noeud(key))
        self.union(nouveau_tas)

    def get_min(self):
        if not self.arbres:
            return None
        min_node = self.arbres[0]
        for arbre in self.arbres:
            if arbre.key < min_node.key:
                min_node = arbre
        return min_node.key

    def extraire_min(self):
        if not self.arbres:
            return None
        min_node = self.arbres[0]
        min_idx = 0
        for i, arbre in enumerate(self.arbres):
            if arbre.key < min_node.key:
                min_node = arbre
                min_idx = i
        del self.arbres[min_idx]
        tas_enfant = TasBinomial()
        tas_enfant.arbres = min_node.children
        self.union(tas_enfant)
        return min_node.key


if __name__ == "__main__":

    # Exemple d'utilisation :
    tokens1 = [10, [12, 11, 1], 5, 22, 99, [20, 70, 60, 65, 23], 6, 4]
    tokens2 = [80, 19, 51, 30, 82, 65, 45, 55, 75, 88, 28, 27, 3, 6, 7, 2]

    tas = TasBinomial()
    tas.inserer(5)
    tas.inserer(3)
    tas.inserer(10)
    tas.inserer(2)
    tas.inserer(12)
    tas.inserer(20)

    print("Min:", tas.get_min())
    print("Extract Min:", tas.extraire_min())
    print("Min:", tas.get_min())