05 — Le tri par tas (heapsort)

Ce que tu vas apprendre

• Ce qu'est un tas binaire et comment il tient dans un tableau
• Comment trier en extrayant le maximum à répétition
• Pourquoi le tri par tas est O(n log n) garanti et en place
• Pourquoi il est pourtant moins utilisé que le tri rapide

Prérequis

• 04 — Tri rapide

Le tri par tas réunit deux qualités que ni la fusion ni le tri rapide n'ont ensemble : il garantit O(n log n) dans tous les cas (contrairement au tri rapide) et il trie en place, sans mémoire supplémentaire (contrairement à la fusion). Il repose sur une structure de données importante, le tas binaire, qu'on étudiera en détail dans la série Structures de données. Ici, on l'utilise comme moteur de tri.

Le tas binaire en deux minutes

Un tas binaire (max-heap) est un arbre binaire avec une règle simple : chaque nœud est supérieur ou égal à ses enfants. La conséquence directe : le plus grand élément est toujours à la racine. C'est exactement ce qu'il faut pour trier, puisqu'on veut extraire les éléments du plus grand au plus petit.

L'astuce, c'est qu'on n'a pas besoin d'une vraie structure d'arbre avec des pointeurs. Un tas se range dans un simple tableau, en utilisant les indices :

• l'élément à l'index i a ses enfants aux index 2i + 1 et 2i + 2 ;
• son parent est à l'index (i - 1) / 2.

Le tas vit donc dans le tableau lui-même, ce qui permet le tri en place.

L'opération clé : le tamisage

Maintenir la propriété du tas repose sur une opération, le tamisage vers le bas (sift down). Quand un élément est trop petit par rapport à ses enfants, on le fait descendre en l'échangeant avec le plus grand de ses enfants, jusqu'à ce qu'il soit à sa place.

typescriptfunction tamiser(arr: number[], n: number, i: number): void {
  let max = i;
  const gauche = 2 * i + 1;
  const droite = 2 * i + 2;
  if (gauche < n && arr[gauche] > arr[max]) max = gauche;
  if (droite < n && arr[droite] > arr[max]) max = droite;
  if (max !== i) {
    [arr[i], arr[max]] = [arr[max], arr[i]];
    tamiser(arr, n, max); // on continue de descendre
  }
}

Le tamisage descend d'un niveau à chaque étape, sur un arbre de hauteur log n : il coûte donc O(log n).

L'algorithme complet

Le tri par tas se fait en deux phases.

pythondef tri_par_tas(arr: list[int]) -> list[int]:
    n = len(arr)
    # Phase 1 : construire le tas (on tamise depuis le dernier parent)
    for i in range(n // 2 - 1, -1, -1):
        tamiser(arr, n, i)
    # Phase 2 : extraire le max et reconstruire, n fois
    for fin in range(n - 1, 0, -1):
        arr[0], arr[fin] = arr[fin], arr[0]  # le max va en fin
        tamiser(arr, fin, 0)                 # on rétablit le tas sur le reste
    return arr

def tamiser(arr, n, i):
    while True:
        max_i = i
        g, d = 2 * i + 1, 2 * i + 2
        if g < n and arr[g] > arr[max_i]: max_i = g
        if d < n and arr[d] > arr[max_i]: max_i = d
        if max_i == i: break
        arr[i], arr[max_i] = arr[max_i], arr[i]
        i = max_i

Phase 1 : on transforme le tableau en tas, en O(n). Phase 2 : n fois, on prend la racine (le maximum), on la place en fin de tableau, et on rétablit le tas sur la partie restante, chaque rétablissement en O(log n). Au total, la phase 2 est en O(n log n), qui domine. Et comme le pivot ne dépend d'aucun hasard ni d'aucune structure de l'entrée, ce coût est garanti dans tous les cas.

Forces, faiblesses, et pourquoi on l'utilise moins

Sur le papier, le tri par tas semble idéal : O(n log n) garanti et O(1) d'espace. Pourtant, en pratique, il est souvent plus lent que le tri rapide. La raison est matérielle : ses accès au tableau sautent d'un index à l'autre (parent, enfants éloignés), ce qui exploite mal le cache du processeur. Le tri rapide, lui, travaille sur des zones contiguës, beaucoup plus efficaces pour le cache.

Le tri par tas garde deux rôles importants. D'abord, comme filet de sécurité dans Introsort : on l'a vu, le std::sort du C++ bascule sur le tri par tas quand le tri rapide menace de dégénérer, ce qui garantit O(n log n) au pire. Ensuite, la structure de tas elle-même, indépendamment du tri, est la base des files de priorité, omniprésentes (Dijkstra, ordonnanceurs, gestion d'événements). On y reviendra dans la série Structures de données.

L'article suivant sort du cadre des tris par comparaison et montre comment, dans des cas particuliers, on peut trier en O(n) avec le tri par comptage et le tri radix.

Sources

• Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7(6). (Paper original)
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapitre 6 "Heapsort". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 2.4 "Priority Queues". Addison-Wesley.
• Musser, D. R. (1997). Introspective Sorting and Selection Algorithms. Software: Practice and Experience, 27(8). (Introsort)