Les k plus grandes valeurs — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 14)

Les

k

plus grandes valeurs

Les tris · niveau 2

Énoncé

Écrire une fonction qui retourne, par ordre décroissant, les $k$ plus grandes valeurs d'un tableau de $n$ valeurs, en $Θ (n lo g k)$ , à l'aide d'un tas min de taille $k$ (on pourra réutiliser la classe de l'exercice 14.6 en y rangeant les opposés des valeurs). Pourquoi un tas min, et non un tas max ?

Corrigé

On garde dans un tas min les $k$ plus grandes valeurs vues jusqu'ici. Sa racine est la plus petite d'entre elles, celle qu'une nouvelle valeur doit battre pour entrer. Avec un tas max, cette valeur serait une feuille quelconque : il faudrait la chercher en $Θ (k)$ . On obtient un tas min en rangeant $- x$ dans le tas max de l'exercice 14.6.


static int[] kPlusGrandes(int[] V, int k) {
    Tas t = new Tas(k);
    for (int x : V) {
        // I : t contient (au signe près) les k plus grandes valeurs vues
        if (t.n < k) t.inserer(-x);
        else if (x > -t.T[0]) { t.extraireMax(); t.inserer(-x); } // x bat le plus petit
    }
    int[] R = new int[t.n];
    for (int i = R.length - 1; i >= 0; i--) R[i] = -t.extraireMax(); // décroissant
    return R;
}


14.7 : 3 plus grandes de [14, 3, 27, 8, 19, 27, 1, 11, 22, 6] = [27, 27, 22]
14.7 : 200 tests aleatoires : true

Chaque valeur coûte au plus une extraction et une insertion dans un tas de taille $k$ : $Θ (n lo g k)$ , mieux que $Θ (n lo g n)$ pour un tri complet quand $k$ est petit, et la mémoire reste en $Θ (k)$ .