Tri par tas en Python
Exemples Python3Le tri par tas est un algorithme de tri conçu en utilisant la structure de données de tas. Un tas est une structure qui approxime un arbre binaire complet et qui satisfait en même temps la propriété de tas : c'est-à-dire que la clé ou l'indice d'un nœud enfant est toujours inférieur (ou supérieur) à celui de son parent. On peut dire que le tri par tas est un tri par sélection qui utilise le concept de tas pour trier.
Exemple
def heapify(arr, n, i):
largest = i
l = 2 * i + 1 # gauche = 2*i + 1
r = 2 * i + 2 # droite = 2*i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # Échange
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Construire un tas max.
for i in range(n, -1, -1):
heapify(arr, n, i)
# Échanger les éléments un par un
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Échanger
heapify(arr, i, 0)
arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Après le tri")
for i in range(n):
print ("%d" %arr[i]),
La sortie de l'exécution du code ci-dessus est :
排序后 5 6 7 11 12 13Autres extensions