Retour au cours

Leçon 35 : Algorithme de Tri par Tas (Heap Sort)

Algorithmes : De Zéro à Héro (Un Guide pour Débutants)

35. Algorithme de Tri par Tas (Heap Sort)

Le Heap Sort est un algorithme de tri efficace basé sur la comparaison qui tire parti de la structure de données Max Heap.

Étapes du Heap Sort

Le Heap Sort comporte deux phases principales :

  1. Construction du Max Heap : Convertir le tableau d'entrée en une structure Max Heap. Ce processus prend un temps O(N).
  2. Phase de Tri : Extraire à plusieurs reprises l'élément maximum (la racine) et le placer à la fin du tableau. Après l'extraction, les éléments restants sont ré-empilés (re-heapified).
    • Échanger la racine (l'élément le plus grand) avec le dernier élément du tas.
    • Réduire la taille du tas d'un.
    • Corriger la propriété de tas sur le nouveau tas, plus petit (un processus appelé heapify), ce qui prend O(log N).

Efficacité

  • Complexité Temporelle : O(N log N) pour tous les cas (Pire, Moyen, Meilleur). C'est parce que la construction prend O(N), et les N extractions/étapes heapify prennent N * O(log N).
  • Complexité Spatiale : Espace auxiliaire O(1), ce qui en fait un algorithme de tri en place (in-place).