You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
138 lines
3.7 KiB
138 lines
3.7 KiB
# coding: utf-8
|
|
|
|
|
|
class Tas:
|
|
class Element:
|
|
def __init__(self, valeur, priorite, index):
|
|
self.valeur = valeur
|
|
self.priorite = priorite
|
|
self.index = index
|
|
|
|
def __str__(self):
|
|
return str(self.valeur)
|
|
|
|
def __init__(self, fonctionPriorite):
|
|
self.L = []
|
|
self.fonctionPriorite = fonctionPriorite
|
|
|
|
def __str__(self):
|
|
s = "["
|
|
for elt in self.L:
|
|
s += " " + str(elt)
|
|
s += "]"
|
|
return s
|
|
|
|
def __parent(self, elt):
|
|
if(elt.index == 0):
|
|
return None
|
|
else:
|
|
return self.L[(elt.index - 1) // 2]
|
|
|
|
def __fils_gauche(self, elt):
|
|
i = 2 * elt.index + 1
|
|
if(i < len(self.L)):
|
|
return self.L[i]
|
|
else:
|
|
return None
|
|
|
|
def __fils_droit(self, elt):
|
|
i = 2 * elt.index + 2
|
|
if(i < len(self.L)):
|
|
return self.L[i]
|
|
else:
|
|
return None
|
|
|
|
def __deplace(self, elt, index):
|
|
assert isinstance(elt, Tas.Element)
|
|
ancien = elt.index
|
|
self.L[index] = elt
|
|
elt.index = index
|
|
return ancien
|
|
|
|
def __promeut(self, elt):
|
|
while(True):
|
|
parent = self.__parent(elt)
|
|
if(parent == None):
|
|
break
|
|
if(parent.priorite >= elt.priorite):
|
|
break
|
|
elt.index = self.__deplace(parent, elt.index)
|
|
self.__deplace(elt, elt.index)
|
|
|
|
def actualise(self, elt):
|
|
assert isinstance(elt, Tas.Element)
|
|
elt.priorite = self.fonctionPriorite(elt.valeur)
|
|
self.__promeut(elt)
|
|
|
|
def ajoute(self, valeur):
|
|
elt = Tas.Element(valeur, self.fonctionPriorite(valeur), len(self.L))
|
|
self.L.append(elt)
|
|
self.__promeut(elt)
|
|
return elt
|
|
|
|
def empty(self):
|
|
return len(self.L) == 0
|
|
|
|
def pop(self):
|
|
n = len(self.L)
|
|
if(n == 0):
|
|
return None
|
|
|
|
tete = self.L[0]
|
|
elt = self.L[n - 1]
|
|
elt.index = 0
|
|
|
|
while True:
|
|
filsGauche = self.__fils_gauche(elt)
|
|
filsDroit = self.__fils_droit(elt)
|
|
plusPrioritaire = elt
|
|
if(filsGauche != None and filsGauche.priorite > plusPrioritaire.priorite):
|
|
plusPrioritaire = filsGauche
|
|
if(filsDroit != None and filsDroit.priorite > plusPrioritaire.priorite):
|
|
plusPrioritaire = filsDroit
|
|
elt.index = self.__deplace(plusPrioritaire, elt.index)
|
|
if(plusPrioritaire is elt):
|
|
break
|
|
self.L.pop()
|
|
return tete.valeur
|
|
|
|
#########################################
|
|
# Exemple d'utilisatio de la classe Tas #
|
|
# Tri de tâches par ordre chronologique #
|
|
#########################################
|
|
|
|
|
|
class Tache:
|
|
'''Tache devant être effectuée avant une date limite'''
|
|
|
|
def __init__(self, jour, nom):
|
|
self.jour = jour
|
|
self.nom = nom
|
|
# Cet attribut servira à accueillir la clé du tas
|
|
self.cle = None
|
|
|
|
def __str__(self):
|
|
return self.nom + " ({})".format(self.jour)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
|
|
# Le niveau de priorité d'un événement x est -x.jour : on trie donc les événements par ordre chronologique
|
|
def calculePriorite(tache):
|
|
return -tache.jour
|
|
|
|
# On crée un tas dont les éléments sont des événements triés par ordre chronologique
|
|
T = Tas(calculePriorite)
|
|
|
|
# Ajoute des événements au tas
|
|
evts = [Tache(5, "T1"), Tache(10, "T2"), Tache(5, "T3"), Tache(3, "T4")]
|
|
for evt in evts:
|
|
evt.cle = T.ajoute(evt)
|
|
|
|
# Supposons que la tache 2 devienne soudain assez urgente
|
|
evts[1].jour = 4
|
|
T.actualise(evts[1].cle)
|
|
|
|
# Retirons dans l'ordre chronologie les éléments du tas
|
|
while(not T.empty()):
|
|
print(T.pop())
|
|
|