Le tri par tas construit un arbre binaire de recherche maximal (max-heap) à partir du tableau, puis extrait répétitivement le maximum pour produire un ordre trié. Il s'exécute en O(n log n) et est sur place.
Un max-heap garde le plus grand élément à la racine. Construire le heap (O(n)), puis échanger la racine à la fin, réduire le heap et réappliquer la propriété du heap (sift down) — n fois.
import heapq
def heap_sort(arr):
heapq.heapify(arr) # min-heap in O(n)
return [heapq.heappop(arr) # pop smallest n times
for _ in range(len(arr))]
heap_sort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
Une implémentation classique le fait sur place en appliquant sift down dans le tableau.
Utilisez-le quand vous avez besoin d'un O(n log n) garanti et d'une mémoire supplémentaire O(1) (merge sort en a besoin d'O(n) ; quicksort risque O(n²)). Il n'est pas stable et a une mauvaise localité de cache, donc il est souvent plus lent en pratique que quicksort. La même structure heap alimente les files de priorité et la recherche des top-k éléments.
Le tri par tas est le seul tri courant qui est à la fois O(n log n) au pire cas et sur place, ce qui le rend précieux dans les contextes à mémoire limitée ou à bornes garanties.
La structure heap en dessous est largement utile — files de priorité, algorithme de Dijkstra et top-k en flux.
Cela consolide l'idée que la bonne structure de données rend un algorithme efficace.