```package sorting;

// tri par tas

public class Heapsort {

// recursive version of moveDown
static void moveDownRec(int[] a, int k, int v, int n) {
int r = 2 * k + 1;
if (r >= n)
a[k] = v;
else {
if (r + 1 < n && a[r] < a[r + 1])
r++;
if (a[r] <= v)
a[k] = v;
else {
a[k] = a[r];
moveDownRec(a, r, v, n);
}
}
}

static void moveDown(int[] a, int i, int x, int n) {
while (true) {
int j = 2 * i + 1;
if (j >= n) break;
if (j + 1 < n && a[j] < a[j + 1]) j++;
if (a[j] <= x) break;
a[i] = a[j];
i = j;
}
a[i] = x;
}

static void heapsort(int[] a) {
int n = a.length;
for (int k = n / 2 - 1; k >= 0; k--)
moveDown(a, k, a[k], n);
for (int k = n - 1; k >= 1; k--) {
int v = a[k];
a[k] = a[0];
moveDown(a, 0, v, k);
}
}

}

class TestHeapsort {

static boolean is_sorted(int[] a) {
for (int i = 1; i < a.length; i++)
if (!(a[i - 1] <= a[i]))
return false;
return true;
}

static final int M = 10; // les éléments sont dans 0..M-1

static int[] occurrences(int[] a) {
int[] occ = new int[M];
for (int i = 0; i < a.length; i++)
occ[a[i]]++;
return occ;
}

static boolean is_permut(int[] occ1, int[] occ2) {
for (int i = 0; i < M; i++)
if (occ1[i] != occ2[i])
return false;
return true;
}

static String print(int[] a) {
String s = "[";
for (int i = 0; i < a.length; i++)
s += (i == 0 ? "" : ", ") + a[i];
return s + "]";
}

static int[] random_array(int len) {
int[] a = new int[len];
for (int i = 0; i < len; i++)
a[i] = (int) (M * Math.random());
return a;
}

static void test(int[] a) {
System.out.println("  test avec       a = " + print(a));
int[] occ1 = occurrences(a);
Heapsort.heapsort(a);
int[] occ2 = occurrences(a);
System.out.println("  heapsort(a) => a = " + print(a));
if (!is_sorted(a)) {
System.out.println("ÉCHEC : le résultat n'est pas trié");
System.exit(1);
}
if (!is_permut(occ1, occ2)) {
System.out.println("ÉCHEC : les éléments diffèrent");
System.exit(1);
}
}

public static void main(String[] args) {
System.out.println("test de mergesort");
for (int len = 0; len < 10; len++)
for (int j = 0; j <= len; j++)
test(random_array(len));
System.out.println("SUCCÈS TestHeapsort");
}

}
```