Motivation

Le tri par tas (Heap Sort) utilise un tas binaire pour trouver de manière répétée le plus grand élément restant en un temps O(log n), offrant ainsi un tri fiable en O(n log n).

Pourquoi apprendre le tri par tas ?

• O(n log n) garanti : contrairement au tri rapide (Quick Sort), il n'a pas de pire cas en O(n²).
• En place : il trie à l'intérieur du tableau d'origine et ne nécessite qu'une mémoire supplémentaire de O(1), contrairement au tri fusion (Merge Sort).
• Intuition du tas : il renforce la compréhension de la manière dont un tas est stocké dans un tableau et comment l'opération de descente (sift-down) le maintient valide.

Si vous avez suivi le cours sur le Tas dans cette série, le tri par tas est cette structure de données mise à profit en tant qu'algorithme de tri.