Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › PriorityQueue : top K et fusion

PriorityQueue : top K et fusion

Piles, files et tasavance

Une PriorityQueue maintient l'accès immédiat au plus petit (ou plus grand) élément, avec insertion et retrait en O(log n).

PriorityQueue<Integer> min = new PriorityQueue<>();                          // tas min
PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder()); // tas max
PriorityQueue<Produit> parPrix = new PriorityQueue<>(Comparator.comparing(Produit::prix));

min.offer(5);   // O(log n)
min.peek();     // O(1) — le minimum
min.poll();     // O(log n) — retire le minimum

Le motif « top K », et son contre-intuitif :

// Garder les K plus GRANDS → tas MIN de taille K
PriorityQueue<Integer> tas = new PriorityQueue<>();
for (int x : flux) {
    tas.offer(x);
    if (tas.size() > k) tas.poll();      // on jette le plus petit des retenus
}

O(n log K) en temps, O(K) en espace : on ne stocke jamais tout le flux. C'est ce qui permet de traiter un flux infini.

La fusion de k listes triées :

PriorityQueue<int[]> tas = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
// [valeur, numéro de liste, index dans la liste]

Le piège : itérer une PriorityQueue avec un for ne donne pas l'ordre de priorité. Seuls des poll() successifs le garantissent.

Les termes à connaître

Tas binaire

Un arbre où chaque parent est inférieur (tas min) ou supérieur (tas max) à ses enfants. offer et poll en O(log n), accès à la racine en O(1).

PriorityQueue

L'implémentation du JDK : tas min par défaut. new PriorityQueue<>(Comparator.reverseOrder()) donne un tas max.

Tas de taille K

Pour garder les K plus grands, on utilise un tas min de taille K : sa tête est le plus faible des retenus, donc celui à évincer. O(n log K).

Fusion de k listes triées

Mettre le premier élément de chaque liste dans un tas, puis répéter : retirer le minimum, insérer son successeur. O(N log k) pour N éléments au total.

Itération non triée

Parcourir une PriorityQueue avec un for ne donne pas l'ordre de priorité : seul poll() répété le garantit. Erreur très fréquente.

Heapify

Construire un tas à partir d'une collection existante coûte O(n), pas O(n log n) : new PriorityQueue<>(collection).

Lire l'explication détaillée et faire le quiz →

Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.