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.
offeretpollen 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
PriorityQueueavec unforne donne pas l'ordre de priorité : seulpoll()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).
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.