Heap Sort
Dernière mise à jour
Le tri par tas traite le tableau comme un tas binaire. Il construit d'abord un max-heap, de sorte que le plus grand élément se trouve à la racine (indice 0). Ensuite il échange à plusieurs reprises la racine avec le dernier élément non trié - fixant le maximum à sa place - et fait descendre la nouvelle racine pour restaurer la propriété de tas. Appuyez sur lecture ci-dessus pour voir la construction du tas et les extractions.
Le tri par tas garantit un temps en O(n log n) comme le tri fusion, mais trie sur place avec seulement O(1) d'espace supplémentaire. Il n'est pas stable et tend à avoir un moins bon comportement de cache que le tri rapide, il est donc souvent choisi lorsqu'une borne garantie et une mémoire constante importent toutes deux.
Complexité en temps et en espace
| Cas | Complexité | Notes |
|---|---|---|
| Meilleur cas | O(n log n) | Construction + n extractions |
| Cas moyen | O(n log n) | Ordre aléatoire |
| Pire cas | O(n log n) | Garanti |
| Espace | O(1) | Sur place |
| Stable | Non | La descente réordonne les éléments égaux |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Construire un max-heap à partir du tableau (descendre depuis le dernier parent). |
| 2 | Échanger la racine (maximum) avec le dernier élément du tas. |
| 3 | Réduire le tas d'un - ce dernier emplacement est maintenant trié. |
| 4 | Faire descendre la nouvelle racine pour restaurer la propriété de max-heap. |
| 5 | Répéter jusqu'à ce que le tas n'ait plus qu'un élément. |
Exemple détaillé
Tri de [3, 1, 6, 5, 2, 4]. La barre | marque la limite entre le tas qui rétrécit et la queue triée :
| Passe | Tableau | Action |
|---|---|---|
| Construire le tas | [6, 5, 4, 1, 2, 3] | Descendre depuis le dernier parent pour construire le max-heap ; 6 est maintenant à la racine. |
| 1 | [5, 3, 4, 1, 2 | 6] | Échanger la racine 6 avec le dernier emplacement, réduire le tas et faire descendre 3. |
| 2 | [4, 3, 2, 1 | 5, 6] | Sortir la racine 5, puis faire descendre 2 pour que 4 remonte à la racine. |
| 3 | [3, 1, 2 | 4, 5, 6] | Sortir la racine 4, puis faire descendre 1 pour que 3 remonte à la racine. |
| 4 | [2, 1 | 3, 4, 5, 6] | Sortir la racine 3 ; 2 satisfait déjà la propriété de tas. |
| 5 | [1 | 2, 3, 4, 5, 6] | Sortir la racine 2 ; il reste un élément, donc le tableau est trié. |
Quand utiliser le tri par tas
| Utilisez-le quand | Évitez-le quand |
|---|---|
Vous avez besoin d'un pire cas garanti en O(n log n) sans risque de O(n²). | Vous avez besoin d'un tri stable qui préserve l'ordre des clés égales. |
La mémoire est limitée - il trie sur place avec seulement O(1) d'espace supplémentaire. | La performance de cache compte et les données tiennent en mémoire - le tri rapide est généralement plus rapide. |
| Vous maintenez déjà un tas (par ex. une file de priorité) sur les données. | Vous voulez le moins de comparaisons - le tri fusion et le tri rapide en font souvent moins en pratique. |
| Une entrée non fiable pourrait déclencher le pire cas du tri rapide et vous ne pouvez pas randomiser. | Les données sont presque triées - le tri par insertion s'exécute en temps quasi linéaire sur elles. |
Code de Heap Sort
Une implémentation propre et exécutable de Heap Sort en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Heap Sort en Python
Python
1def heap_sort(a):2 n = len(a)3 # Build a max-heap, deepest parent first4 for i in range(n // 2 - 1, -1, -1):5 sift_down(a, i, n)6 # Repeatedly move the max to the end and shrink the heap7 for end in range(n - 1, 0, -1):8 a[0], a[end] = a[end], a[0]9 sift_down(a, 0, end)10 return a11
12
13def sift_down(a, i, size):14 while True:15 largest = i16 left, right = 2 * i + 1, 2 * i + 217 if left < size and a[left] > a[largest]:18 largest = left19 if right < size and a[right] > a[largest]:20 largest = right21 if largest == i:22 return23 a[i], a[largest] = a[largest], a[i]24 i = largest25
26
27nums = [12, 11, 13, 5, 6, 7]28print("Before:", nums)29heap_sort(nums)30print("After: ", nums)Code de Heap Sort en JavaScript
JavaScript
1function heapSort(a) {2 const n = a.length;3 // Build a max-heap, then repeatedly move the max to the end4 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);5 for (let end = n - 1; end > 0; end--) {6 [a[0], a[end]] = [a[end], a[0]];7 siftDown(a, 0, end);8 }9 return a;10}11
12function siftDown(a, i, size) {13 while (true) {14 const left = 2 * i + 1;15 const right = 2 * i + 2;16 let largest = i;17 if (left < size && a[left] > a[largest]) largest = left;18 if (right < size && a[right] > a[largest]) largest = right;19 if (largest === i) return;20 [a[i], a[largest]] = [a[largest], a[i]];21 i = largest;22 }23}24
25const data = [5, 2, 9, 1, 7, 3];26console.log("Before:", data);27console.log("Sorted:", heapSort([...data]));Code de Heap Sort en Java
Java
1import java.util.Arrays;2
3public class Main {4 static void heapSort(int[] arr) {5 int n = arr.length;6 // Build a max-heap, deepest parent first7 for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);8 // Repeatedly move the max to the end and shrink the heap9 for (int end = n - 1; end > 0; end--) {10 swap(arr, 0, end);11 siftDown(arr, 0, end);12 }13 }14
15 static void siftDown(int[] arr, int i, int size) {16 while (true) {17 int largest = i, l = 2 * i + 1, r = 2 * i + 2;18 if (l < size && arr[l] > arr[largest]) largest = l;19 if (r < size && arr[r] > arr[largest]) largest = r;20 if (largest == i) return;21 swap(arr, i, largest);22 i = largest;23 }24 }25
26 static void swap(int[] arr, int a, int b) {27 int tmp = arr[a];28 arr[a] = arr[b];29 arr[b] = tmp;30 }31
32 public static void main(String[] args) {33 int[] arr = {12, 11, 13, 5, 6, 7};34 System.out.println("Before: " + Arrays.toString(arr));35 heapSort(arr);36 System.out.println("After: " + Arrays.toString(arr));37 }38}Code de Heap Sort en C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void siftDown(std::vector<int>& a, int n, int i) {11 while (true) {12 int largest = i, l = 2 * i + 1, r = 2 * i + 2;13 if (l < n && a[l] > a[largest]) largest = l;14 if (r < n && a[r] > a[largest]) largest = r;15 if (largest == i) return;16 std::swap(a[i], a[largest]);17 i = largest;18 }19}20
21void heapSort(std::vector<int>& a) {22 int n = static_cast<int>(a.size());23 // Build a max-heap in place24 for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i);25 // Repeatedly move the max to the end and shrink the heap26 for (int end = n - 1; end > 0; --end) {27 std::swap(a[0], a[end]);28 siftDown(a, end, 0);29 }30}31
32int main() {33 std::vector<int> data = {12, 11, 13, 5, 6, 7};34 std::cout << "Before: ";35 printVec(data);36 heapSort(data);37 std::cout << "After: ";38 printVec(data);39 return 0;40}Code de Heap Sort en C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void siftDown(int a[], int n, int i) {9 while (1) {10 int largest = i, l = 2 * i + 1, r = 2 * i + 2;11 if (l < n && a[l] > a[largest]) largest = l;12 if (r < n && a[r] > a[largest]) largest = r;13 if (largest == i) return;14 int tmp = a[i];15 a[i] = a[largest];16 a[largest] = tmp;17 i = largest;18 }19}20
21void heapSort(int a[], int n) {22 // Build a max-heap in place23 for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);24 // Repeatedly move the max to the end and shrink the heap25 for (int end = n - 1; end > 0; end--) {26 int tmp = a[0];27 a[0] = a[end];28 a[end] = tmp;29 siftDown(a, end, 0);30 }31}32
33int main(void) {34 int data[] = {12, 11, 13, 5, 6, 7};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 heapSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}FAQ sur le tri par tas
Quelle est la complexité temporelle du tri par tas ?
Le tri par tas est en
O(n log n) dans le meilleur, le moyen et le pire cas. Construire le tas est en O(n) et chacune des n extractions coûte O(log n). Il utilise O(1) d'espace supplémentaire.Le tri par tas est-il stable ?
Non. L'opération de descente peut déplacer des éléments égaux l'un par-dessus l'autre, si bien que le tri par tas ne préserve pas l'ordre relatif des clés égales.
Quand devrais-je utiliser le tri par tas ?
Utilisez le tri par tas lorsque vous avez besoin d'un pire cas garanti en
O(n log n) avec seulement O(1) de mémoire supplémentaire. Il évite le risque de O(n²) du tri rapide sans le tampon en O(n) du tri fusion, au prix de la stabilité et de la performance de cache.Quelle est la différence entre le tri par tas et le tri rapide ?
Les deux trient sur place, mais le tri rapide a un pire cas en
O(n²) tandis que le tri par tas garantit O(n log n). En pratique le tri rapide est généralement plus rapide grâce à une meilleure localité de cache et moins d'échanges, si bien que le tri par tas est surtout préféré lorsque la borne du pire cas doit être garantie.Quel est le lien entre le tri par tas et une file de priorité ?
Un tas binaire est l'implémentation standard d'une file de priorité, et le tri par tas revient essentiellement à extraire à plusieurs reprises le maximum de cette file. Si vous conservez déjà vos données dans un tas, en extraire les éléments un par un vous donne un ordre trié gratuitement.
Le tri par tas nécessite-t-il un max-heap ou un min-heap ?
Pour trier en ordre croissant sur place, utilisez un max-heap : le plus grand élément est échangé à la fin à chaque passe, faisant croître la queue triée depuis la droite. Un min-heap produirait un ordre décroissant sur place, ou croissant si vous extrayez dans un tableau séparé.
Ressources associées
Plus de visualisations
