Optimisation du tri par tas
Dans le tri par tas de la section précédente, nous avons alloué de l'espace supplémentaire pour construire le tas et le trier. Dans cette section, nous optimisons cela en utilisant un tri par tas en place.
Pour un tas max, échangez d'abord les données à la position de départ avec la valeur à la fin du tableau, de sorte que la fin du tableau devienne l'élément maximal. Effectuez ensuite une opération de descente (shift down) sur l'élément W pour régénérer le tas max. Ensuite, échangez la valeur maximale nouvellement générée avec l'avant-dernière position du tableau entier, de sorte que l'avant-dernière position contienne la deuxième plus grande donnée. Ce processus se poursuit par analogie.
L'ensemble du processus peut être illustré par le diagramme suivant :

Exemple de code Java
Téléchargement du paquet de code source :Télécharger
Code du fichier src/example/heap/HeapSort.java :
import example.sort.SortTestHelper;
/**
Tri par tas en place
*/
public class HeapSort<T extends Comparable> {
public static void sort(Comparable[] arr) {
int n = arr.length;
// Notez que notre tas est indexé à partir de 0 à ce stade
// Commencez à partir de (indice du dernier élément - 1) / 2
// L'indice du dernier élément est n-1
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
shiftDown(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
shiftDown(arr, i, 0);
}
}
// Échanger les deux éléments aux indices i et j dans le tas
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// Processus shiftDown d'origine
private static void shiftDown(Comparable[] arr, int n, int k) {
while (2 * k + 1 < n) {
// Nœud enfant gauche
int j = 2 * k + 1;
// Le nœud enfant droit est plus grand que le nœud enfant gauche
if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0)
j += 1;
// Plus grand que les deux nœuds enfants
if (arr[k].compareTo(arr[j]) >= 0) break;
// Échanger les valeurs du nœud d'origine et du nœud enfant
swap(arr, k, j);
k = j;
}
}
// Test de HeapSort
public static void main(String[] args) {
int N = 100;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
sort(arr);
// Extraire progressivement les données dans heapify à l'aide de extractMax
// L'ordre d'extraction doit être du plus grand au plus petit
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
// S'assurer que le tableau arr est trié du plus grand au plus petit
for (int i = 1; i < N; i++)
assert arr[i - 1] >= arr[i];
}
}