File de priorité

Le père de la case $i>0$ est la case $(i-1)/2$, ses fils sont les cases $2i+1$ et $2i+2$.

class Tas {
    int[] T; int n;                       // le tas occupe T[0:n]
    Tas(int capacite) { T = new int[capacite]; n = 0; }

    void inserer(int x) {
        if (n == T.length) T = Arrays.copyOf(T, 2 * n + 1); // agrandir
        T[n] = x; int i = n; n++;
        // I(i) : T[0:n] est un tas, sauf peut-être entre i et son père
        while (i > 0 && T[(i - 1) / 2] < T[i]) {
            echanger(T, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    int extraireMax() {                   // tas non vide
        int max = T[0];
        n--;
        T[0] = T[n];                      // la dernière valeur va à la racine
        int i = 0;
        // I(i) : T[0:n] est un tas, sauf peut-être entre i et ses fils
        while (2 * i + 1 < n) {
            int f = 2 * i + 1;
            if (f + 1 < n && T[f + 1] > T[f]) f++;  // le plus grand fils
            if (T[i] >= T[f]) break;
            echanger(T, i, f); i = f;
        }
        return max;
    }
}

14.6 : tas = [20, 12, 12, 5, 9, 3, 7]
14.6 : extractions : 20 12 12 9 7 5 3

nom : T
valeurs : 12 9 3 5 20
colorier : 4
fleches : 4->1 1->0
legende : insertion de 20 en case 4 : il remonte en case 1, puis à la racine

nom : T
valeurs : 20 12 12 5 9 3 7
fleches : 0->1 1->3 2->5
fleches-bas : 0->2 1->4 2->6
legende : le tas obtenu : chaque père i est ≥ ses fils 2i+1 et 2i+2

Une valeur qui remonte ou descend parcourt au plus une branche de l'arbre presque complet, de hauteur $\lfloor {\log }_{2}n\rfloor$ : chaque opération est en $\Theta (\log n)$ dans le pire cas. Les extractions successives donnent les valeurs par ordre décroissant : c'est le principe du tri par tas.