class HeapError(IndexError):
pass
class Heap(object):
"""Un tas est un arbre binaire presque équilibré dans lequel tout noeud a
une valeur inférieure à celles de ses fils.
L'hypothèse de presque équilibrage permet d'implémenter l'arbre par un
tableau : les éléments sont listés en partant de la racine (d'index 0 dans
le tableau) et en parcourant l'arbre étage par étage, de gauche à droite ;
le fils gauche d'un noeud d'index i se trouve donc à l'index 2i + 1, le
fils droit à l'index 2i + 2 et le père à l'index (i - 1)/2. Le dernier
noeud (le plus à droite du dernier étage de l'arbre) est le dernier élément
du tableau."""
def __init__(self, l = ()):
"""Initialisation d'un tas : l est une liste de valeurs à stocker dans
le tas."""
self.table = [] self.size = 0
for v in l:
self.push(v)
def push(self, val):
"""Ajout d'une valeur val dans le tas : on commence par placer la
valeur en fin de tas, puis on la fait descendre le long de la branche
de l'arbre de façon à respecter la propriété de tas"""
index = self.size self.table.append(val) self.size += 1
while index > 0:
father_index = (index - 1)/2
father = self.table[father_index]
if father <= val:
break
else:
self.table[index] = father
self.table[father_index] = val
index = father_index
def pop(self):
"""Suppression de la valeur à la racine du tas : on supprime le dernier
élément du tas après avoir sauvé sa valeur à la racine, puis on percole
pour redisposer cette valeur à sa place"""
if len(self.table) == 0:
raise HeapError("Tas vide")
popped_val = self.table[0]
last_index = self.size - 1
self.table[0] = self.table[last_index]
del(self.table[last_index])
self.size = last_index
if self.size > 0:
self.percolate(0)
return popped_val
def percolate(self, index):
"""Percolation : la valeur localisée au noeud identifié par index n'est
pas à sa place mais les deux sous-arbres sont des tas ; il faut faire
monter la valeur pour respecter la propriété de tas"""
current = self.table[index] left_index = 2*index + 1 right_index = 2*index + 2
if right_index < self.size:
left = self.table[left_index] right = self.table[right_index]
if left < current and left <= right:
self.table[left_index] = current
self.table[index] = left
self.percolate(left_index)
elif right < current and right <= left:
self.table[right_index] = current
self.table[index] = right
self.percolate(right_index)
elif left_index < self.size:
left = self.table[left_index]
if left < current:
self.table[left_index] = current
self.table[index] = left