VecDeque et BinaryHeap en Rust

Pensez à la file d’attente d’un café. Les nouveaux clients se placent au bout, et le barista sert celui qui est devant. Pensez maintenant à la salle d’attente des urgences. Là, le patient le plus grave passe en premier, peu importe quand il est arrivé. Dans les deux cas, on fait la queue, mais les règles ne sont pas les mêmes.

Rust a une collection pour chacune. Une VecDeque est une file rapide où vous pouvez ajouter et retirer aux deux bouts. Un BinaryHeap (tas binaire) est une file de priorité : il vous donne toujours l’élément le plus grand (ou le plus urgent) en premier. Vous connaissez déjà les vecteurs, et la page HashSet vous a donné un premier aperçu de VecDeque. Cette page va plus loin, et ajoute BinaryHeap par-dessus.

Pourquoi un Vec fait une mauvaise file

Vous pouvez utiliser un Vec comme file d’attente. On ajoute avec push, on retire du début avec remove(0). Ça marche. Le problème, c’est ce qui se passe en coulisses.

Un Vec garde ses éléments serrés les uns contre les autres, à partir de la position 0. Quand vous retirez le premier, tous les autres doivent glisser d’une case vers la gauche pour boucher le trou. Avec 3 éléments, personne ne le remarque. Avec 100 000 éléments, chaque remove(0) déplace 99 999 valeurs. C’est ce que veut dire « O(n) » : le travail grandit avec la taille de la liste.

Une VecDeque (prononcez « vec dèque », pour double-ended queue, « file à deux bouts ») règle ce problème avec un tampon circulaire (ring buffer). Imaginez une table ronde aux places numérotées, avec un petit panneau « la file commence ici ». Quand la première personne s’en va, personne ne se lève : on déplace simplement le panneau vers la place suivante. Quand quelqu’un arrive et que la dernière place est prise, il s’assoit à la place 0 si elle est libre, en faisant le tour de la table. Ajouter ou retirer à l’un des deux bouts revient à « déplacer le panneau » ou « occuper une place », donc cela prend le même temps minuscule, quelle que soit la longueur de la file. C’est ça, « O(1) ».

use std::collections::VecDeque;

fn main() {
    // Un Vec utilisé comme file : ça marche, mais remove(0) décale tout le monde vers la gauche.
    let mut vec_line = vec!["Ana", "Ben", "Cai"];
    let served = vec_line.remove(0);
    println!("Vec a servi {served}, encore en attente : {:?}", vec_line);

    // Une VecDeque : pop_front déplace juste son repère de « début ».
    let mut deque_line = VecDeque::from(vec!["Ana", "Ben", "Cai"]);
    let served = deque_line.pop_front();
    println!("VecDeque a servi {:?}, encore en attente : {:?}", served, deque_line);
}

Sortie :

Vec a servi Ana, encore en attente : ["Ben", "Cai"]
VecDeque a servi Some("Ana"), encore en attente : ["Ben", "Cai"]

▶ Essayez par vous-même

Le résultat est le même. La différence, c’est la vitesse, et elle n’apparaît que quand la file devient longue. Remarquez aussi une chose : pop_front renvoie une Option. Si la file est vide, vous obtenez None au lieu d’un plantage.

Les bases de VecDeque

VecDeque se trouve dans std::collections, il faut donc une ligne use. Ensuite, les méthodes se lisent presque comme de l’anglais : push (ajouter) ou pop (retirer), au début (front) ou à la fin (back).

use std::collections::VecDeque;

fn main() {
    let mut deque: VecDeque<i32> = VecDeque::new();
    deque.push_back(2);
    deque.push_back(3);
    deque.push_front(1);
    println!("{:?}", deque);

    println!("devant : {:?}, derrière : {:?}", deque.front(), deque.back());
    println!("longueur : {}, vide : {}", deque.len(), deque.is_empty());
    println!("deque[1] = {}", deque[1]);
    println!("get(9) = {:?}", deque.get(9));

    let first = deque.pop_front();
    let last = deque.pop_back();
    println!("retirés : {:?} et {:?}, reste : {:?}", first, last, deque);
}

Sortie :

[1, 2, 3]
devant : Some(1), derrière : Some(3)
longueur : 3, vide : false
deque[1] = 2
get(9) = None
retirés : Some(1) et Some(3), reste : [2]

▶ Essayez par vous-même

front et back vous permettent de regarder sans retirer. L’indexation avec deque[1] fonctionne comme pour un Vec, et provoque un panic si l’indice est trop grand : utilisez donc get quand vous n’êtes pas sûr.

Vous pouvez aussi construire une VecDeque à partir d’un Vec, la parcourir avec une boucle, et la retransformer en Vec ou en slice quand une autre fonction en a besoin :

use std::collections::VecDeque;

fn main() {
    let mut playlist = VecDeque::from(vec!["Intro", "Couplet", "Refrain"]);
    playlist.push_front("Décompte");
    playlist.push_back("Outro");

    for (i, song) in playlist.iter().enumerate() {
        println!("{}. {}", i + 1, song);
    }

    // Besoin d'une slice normale ? make_contiguous remet tout bout à bout en mémoire.
    let songs = playlist.make_contiguous();
    songs.sort();
    println!("trié : {:?}", songs);

    // Ou retransformez le tout en Vec.
    let as_vec: Vec<&str> = playlist.into();
    println!("en Vec : {:?}", as_vec);
}

Sortie :

1. Décompte
2. Intro
3. Couplet
4. Refrain
5. Outro
trié : ["Couplet", "Décompte", "Intro", "Outro", "Refrain"]
en Vec : ["Couplet", "Décompte", "Intro", "Outro", "Refrain"]

▶ Essayez par vous-même

Pourquoi a-t-on besoin de make_contiguous ? Souvenez-vous de la table ronde : après avoir fait le tour, les éléments peuvent se retrouver en deux morceaux séparés en mémoire. make_contiguous les range en un seul morceau et vous rend une slice normale, pour que vous puissiez utiliser les outils des slices comme sort. Vous n’en aurez pas souvent besoin, mais c’est bon de savoir que ça existe.

VecDeque dans la vraie vie

Voici trois usages courants où une VecDeque tombe pile.

Une file de tâches « premier arrivé, premier servi ». Des documents attendent leur tour pour être imprimés. Les nouveaux vont au bout, l’imprimante prend celui du début. Un document urgent peut quand même passer devant avec push_front :

use std::collections::VecDeque;

fn main() {
    let mut print_queue = VecDeque::new();
    print_queue.push_back("rapport.pdf");
    print_queue.push_back("photo.jpg");
    print_queue.push_back("facture.pdf");

    // Urgent ! Celui-ci passe en tête de file.
    print_queue.push_front("carte-embarquement.pdf");

    while let Some(job) = print_queue.pop_front() {
        println!("Impression de {job} ({} en attente)", print_queue.len());
    }
    println!("Terminé. File vide : {}", print_queue.is_empty());
}

Sortie :

Impression de carte-embarquement.pdf (3 en attente)
Impression de rapport.pdf (2 en attente)
Impression de photo.jpg (1 en attente)
Impression de facture.pdf (0 en attente)
Terminé. File vide : true

▶ Essayez par vous-même

while let Some(job) = ...pop_front() est la boucle de file classique. Elle continue jusqu’à ce que pop_front renvoie None, c’est-à-dire jusqu’à ce que la file soit vide. (Voyez if let si cette forme est nouvelle pour vous.)

Un historique des N derniers éléments. Une barre de recherche qui retient vos 3 recherches les plus récentes. Quand elle est pleine, la plus ancienne tombe par le début :

use std::collections::VecDeque;

const MAX_RECENT: usize = 3;

fn remember(recent: &mut VecDeque<String>, search: &str) {
    if recent.len() == MAX_RECENT {
        recent.pop_front(); // oublier la recherche la plus ancienne
    }
    recent.push_back(search.to_string());
}

fn main() {
    let mut recent = VecDeque::with_capacity(MAX_RECENT);

    for search in ["livre rust", "vecdeque", "tas binaire", "pizza près de chez moi"] {
        remember(&mut recent, search);
        println!("{:?}", recent);
    }

    // Afficher la plus récente en premier, comme le ferait une barre de recherche.
    let newest_first: Vec<&String> = recent.iter().rev().collect();
    println!("plus récentes d'abord : {:?}", newest_first);
}

Sortie :

["livre rust"]
["livre rust", "vecdeque"]
["livre rust", "vecdeque", "tas binaire"]
["vecdeque", "tas binaire", "pizza près de chez moi"]
plus récentes d'abord : ["pizza près de chez moi", "tas binaire", "vecdeque"]

▶ Essayez par vous-même

Une moyenne glissante. Un thermomètre envoie une mesure chaque minute, et vous voulez la moyenne des 3 dernières. Chaque nouvelle mesure entre par la fin, et la plus ancienne sort par le début. En tenant une somme courante (sum), vous n’avez jamais besoin de réadditionner toute la fenêtre :

use std::collections::VecDeque;

fn main() {
    let readings = [20.0, 22.0, 24.0, 23.0, 19.0, 21.0];
    let window_size = 3;
    let mut window: VecDeque<f64> = VecDeque::new();
    let mut sum = 0.0;

    for reading in readings {
        window.push_back(reading);
        sum += reading;

        if window.len() > window_size {
            sum -= window.pop_front().unwrap(); // la mesure la plus ancienne s'en va
        }

        if window.len() == window_size {
            let average = sum / window_size as f64;
            println!("{:?} -> moyenne {:.1}", window, average);
        }
    }
}

Sortie :

[20.0, 22.0, 24.0] -> moyenne 22.0
[22.0, 24.0, 23.0] -> moyenne 23.0
[24.0, 23.0, 19.0] -> moyenne 22.0
[23.0, 19.0, 21.0] -> moyenne 21.0

▶ Essayez par vous-même

Le unwrap() est sans danger ici : on ne retire un élément que quand la fenêtre en contient plus de 3, elle ne peut donc pas être vide.

BinaryHeap : toujours le plus grand d’abord

Passons à la salle d’attente des urgences. Parfois, peu importe qui est arrivé en premier. Vous voulez « donne-moi la chose la plus importante », encore et encore, pendant que de nouvelles choses continuent d’arriver.

Vous pourriez tout mettre dans un Vec et le trier à chaque fois. Mais tout trier juste pour trouver l’élément du dessus, c’est beaucoup de travail gaspillé. Un BinaryHeap garde ses éléments organisés de façon seulement approximative, juste assez pour que le plus grand soit toujours au sommet. Ajouter un élément ou prendre celui du sommet coûte peu (O(log n), qui grandit très lentement : environ 17 étapes pour 100 000 éléments).

Le BinaryHeap de Rust est un tas max (max-heap) : pop vous donne toujours la plus grande valeur. Voici les offres d’une vente aux enchères :

use std::collections::BinaryHeap;

fn main() {
    let mut bids = BinaryHeap::new();
    bids.push(120);
    bids.push(450);
    bids.push(80);
    bids.push(300);

    println!("meilleure offre : {:?}", bids.peek());
    println!("nombre d'offres : {}", bids.len());

    while let Some(bid) = bids.pop() {
        println!("suivante : {bid}");
    }

    let heap = BinaryHeap::from(vec![5, 1, 4, 2, 3]);
    println!("trié : {:?}", heap.into_sorted_vec());
}

Sortie :

meilleure offre : Some(450)
nombre d'offres : 4
suivante : 450
suivante : 300
suivante : 120
suivante : 80
trié : [1, 2, 3, 4, 5]

▶ Essayez par vous-même

peek regarde le sommet sans le retirer. pop le retire. into_sorted_vec consomme le tas et vous donne un Vec trié du plus petit au plus grand. Comme avec VecDeque, peek et pop renvoient une Option : un tas vide ne provoque jamais de plantage.

Des tas min avec Reverse

Et si vous voulez le plus petit d’abord ? L’arrêt de livraison le plus proche, le vol le moins cher, l’échéance la plus proche. Pas besoin d’une autre collection. Enveloppez chaque valeur dans std::cmp::Reverse, qui inverse simplement la comparaison : ce qui était le plus grand devient le plus petit.

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    // Arrêts de livraison, par distance en km. On va toujours au plus proche.
    let mut stops = BinaryHeap::new();
    for km in [12, 3, 8, 5] {
        stops.push(Reverse(km));
    }

    if let Some(Reverse(closest)) = stops.peek() {
        println!("arrêt le plus proche : {closest} km");
    }

    while let Some(Reverse(km)) = stops.pop() {
        println!("trajet de {km} km");
    }
}

Sortie :

arrêt le plus proche : 3 km
trajet de 3 km
trajet de 5 km
trajet de 8 km
trajet de 12 km

▶ Essayez par vous-même

Reverse(km) est une toute petite struct enveloppe. Le pattern (motif) Some(Reverse(km)) déballe les deux couches d’un coup, et vous récupérez le nombre tout simple.

Une file de priorité de structs

Les vraies tâches ne sont pas que des nombres. Elles ont un nom, une priorité, peut-être une heure d’arrivée. Pour mettre votre propre struct dans un BinaryHeap, Rust doit savoir comment en comparer deux, ce qui veut dire que la struct doit implémenter Ord (voir Les traits courants).

Le plus rapide est d’utiliser derive. Une chose à savoir : derive compare les champs de haut en bas. Il compare le premier champ, et ne regarde le deuxième que si les premiers sont égaux. Mettez donc en premier le champ selon lequel vous voulez trier :

use std::collections::BinaryHeap;

// L'ordre des champs compte : derive compare d'abord `priority`, puis `name`.
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Task {
    priority: u8,
    name: String,
}

fn main() {
    let mut todo = BinaryHeap::new();
    todo.push(Task { priority: 2, name: "prendre rendez-vous chez le dentiste".to_string() });
    todo.push(Task { priority: 5, name: "réparer la panne".to_string() });
    todo.push(Task { priority: 1, name: "arroser les plantes".to_string() });
    todo.push(Task { priority: 2, name: "répondre à un e-mail".to_string() });

    while let Some(task) = todo.pop() {
        println!("[{}] {}", task.priority, task.name);
    }
}

Sortie :

[5] réparer la panne
[2] répondre à un e-mail
[2] prendre rendez-vous chez le dentiste
[1] arroser les plantes

▶ Essayez par vous-même

Si vous échangiez les deux champs pour que name vienne en premier, le tas rangerait les tâches par ordre alphabétique et ignorerait presque complètement la priorité. Erreur facile, bug silencieux.

Regardez les deux tâches de priorité 2. La tâche « prendre rendez-vous chez le dentiste » est arrivée la première, mais c’est « répondre à un e-mail » qui est sortie en premier. L’égalité a été départagée par name, et « répondre » passe devant « prendre » parce qu’il vient plus loin dans l’alphabet. C’est prévisible, mais ce n’est sans doute pas ce que vous voulez. En général, en cas d’égalité, la tâche arrivée la première devrait passer d’abord. Pour ce genre de règle sur mesure, écrivez Ord vous-même :

use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Debug, PartialEq, Eq)]
struct Job {
    priority: u8,
    id: u32, // ordre d'arrivée : un id plus petit est arrivé plus tôt
    name: String,
}

impl Ord for Job {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority
            .cmp(&other.priority) // la priorité la plus haute gagne
            .then_with(|| other.id.cmp(&self.id)) // en cas d'égalité, l'id le plus ancien gagne
    }
}

impl PartialOrd for Job {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut jobs = BinaryHeap::new();
    jobs.push(Job { priority: 2, id: 1, name: "prendre rendez-vous chez le dentiste".to_string() });
    jobs.push(Job { priority: 5, id: 2, name: "réparer la panne".to_string() });
    jobs.push(Job { priority: 1, id: 3, name: "arroser les plantes".to_string() });
    jobs.push(Job { priority: 2, id: 4, name: "répondre à un e-mail".to_string() });

    while let Some(job) = jobs.pop() {
        println!("[{}] #{} {}", job.priority, job.id, job.name);
    }
}

Sortie :

[5] #2 réparer la panne
[2] #1 prendre rendez-vous chez le dentiste
[2] #4 répondre à un e-mail
[1] #3 arroser les plantes

▶ Essayez par vous-même

L’astuce est dans then_with : si les priorités sont égales, on compare les ids à l’envers (other.id contre self.id). Le plus petit id compte alors comme « plus grand », et il sort donc le premier du tas max. Ne vous inquiétez pas s’il vous faut une minute pour digérer ça. Inverser la comparaison, c’est exactement ce que Reverse fait pour vous, mais écrit à la main. Le bloc PartialOrd est toujours le même code passe-partout : il appelle simplement votre cmp.

Un vrai algorithme : les 3 meilleurs scores

Imaginons une énorme liste de scores de jeu dont vous ne voulez que les 3 meilleurs. Trier toute la liste fonctionne, mais il existe une astuce élégante qui ne garde jamais plus de quelques éléments.

Utilisez un tas min de taille 3. Ajoutez chaque score. Quand le tas contient 4 éléments, retirez-en un. Comme c’est un tas min, celui que vous jetez est le plus petit. À la fin, il ne reste que les 3 meilleurs.

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let scores = [72, 95, 64, 88, 91, 55, 99, 80];
    let mut top = BinaryHeap::new(); // un tas min : le plus petit score est au sommet

    for score in scores {
        top.push(Reverse(score));
        if top.len() > 3 {
            top.pop(); // quatre, c'est un de trop : on jette le plus petit
        }
    }

    let best: Vec<u32> = top
        .into_sorted_vec()
        .into_iter()
        .map(|Reverse(score)| score)
        .collect();
    println!("top 3 : {:?}", best);
}

Sortie :

top 3 : [99, 95, 91]

▶ Essayez par vous-même

Petit bonus : into_sorted_vec trie les valeurs Reverse du « plus petit » au « plus grand », ce qui, pour les vrais scores, veut dire du plus grand au plus petit. Le meilleur score sort donc en premier, sans tri supplémentaire. Ce pattern fonctionne pour une liste d’un million de scores, tout en ne gardant jamais plus de 4 éléments en mémoire.

Laquelle choisir ?

Voici un aide-mémoire. « Rapide » veut dire que le temps reste à peu près le même, quelle que soit la taille de la collection. « Lent » veut dire qu’il grandit avec la taille.

Collection	Idéale pour	Ajouter	Prendre au début / au sommet	Trouver un élément quelconque
Vec<T>	Une liste lue par position ; une pile	Rapide à la fin	Lent (remove(0) décale tout)	Lent (examine chaque élément)
VecDeque<T>	Les files : ajouter et retirer aux deux bouts	Rapide aux deux bouts	Rapide aux deux bouts	Lent (examine chaque élément)
BinaryHeap<T>	« Donne-moi le plus grand / le plus urgent »	Assez rapide (O(log n))	Assez rapide : toujours le plus grand	Lent, et pas d’ordre trié
BTreeSet<T>	Des valeurs uniques, toujours triées	Assez rapide (O(log n))	Assez rapide : le plus petit et le plus grand	Assez rapide (O(log n))

Dans le doute, commencez par un Vec. Passez à une VecDeque quand vous retirez des éléments par le début. Passez à un BinaryHeap quand vous vous demandez sans cesse « qu’est-ce qui est le plus important maintenant ? ». Utilisez un BTreeSet quand il vous faut des valeurs uniques et triées et que vous voulez y chercher des éléments, pas seulement prendre celui du sommet.

Erreurs courantes

Croire que .iter() sur un BinaryHeap est trié. Un tas n’est ordonné que de façon approximative. Le plus grand élément est en premier, mais les autres sont dans un désordre utile au tas, pas à vous :

use std::collections::BinaryHeap;

fn main() {
    let heap = BinaryHeap::from(vec![1, 5, 2, 8, 3, 9]);

    println!("iter    : {:?}", heap.iter().collect::<Vec<_>>());
    println!("trié    : {:?}", heap.clone().into_sorted_vec());

    let mut heap = heap;
    print!("retirés :");
    while let Some(n) = heap.pop() {
        print!(" {n}");
    }
    println!();
}

Sortie :

iter    : [9, 8, 2, 5, 3, 1]
trié    : [1, 2, 3, 5, 8, 9]
retirés : 9 8 5 3 2 1

▶ Essayez par vous-même

C’est pareil quand vous affichez un tas avec {:?} : vous verrez le désordre interne. Si vous avez besoin des éléments dans l’ordre, retirez-les un par un avec pop, ou appelez into_sorted_vec.

Mettre dans un BinaryHeap une struct sans Ord. Le tas doit comparer les éléments pour savoir lequel va au sommet. Si votre struct ne peut pas être comparée, Rust vous arrête :

use std::collections::BinaryHeap;

struct Ticket {
    urgency: u8,
    title: String,
}

fn main() {
    let mut tickets = BinaryHeap::new();
    tickets.push(Ticket { urgency: 3, title: "connexion impossible".to_string() });
}

error[E0277]: the trait bound `Ticket: Ord` is not satisfied
  --> src/main.rs:10:13
   |
10 |     tickets.push(Ticket { urgency: 3, title: "connexion impossible".to_string() });
   |             ^^^^ the trait `Ord` is not implemented for `Ticket`
   |
help: consider annotating `Ticket` with `#[derive(Ord)]`

Le compilateur dit que le trait Ord n’est pas implémenté pour Ticket. La solution est d’ajouter #[derive(PartialEq, Eq, PartialOrd, Ord)] au-dessus de la struct (Ord a aussi besoin des trois autres), avec urgency comme premier champ. Ou d’écrire Ord à la main, comme dans l’exemple Job plus haut.

Exercices

1. Chacun son tour

Trois amis, Ana, Ben et Cai, jouent à tour de rôle à un jeu de société. Mettez-les dans une VecDeque et affichez qui joue aux tours 1 à 5. Après chaque tour, le joueur retourne au bout de la file. Indice : retirez le joueur avec pop_front, affichez-le, puis remettez-le avec push_back.

Voir la solution

use std::collections::VecDeque;

fn main() {
    let mut players = VecDeque::from(vec!["Ana", "Ben", "Cai"]);

    for turn in 1..=5 {
        let player = players.pop_front().unwrap();
        println!("Tour {turn} : {player}");
        players.push_back(player); // retour au bout de la file
    }
}

Sortie :

Tour 1 : Ana
Tour 2 : Ben
Tour 3 : Cai
Tour 4 : Ana
Tour 5 : Ben

▶ Essayez par vous-même

Le début et la fin sont tous les deux rapides dans une VecDeque, donc faire tourner la file ne coûte presque rien, quel que soit le nombre de joueurs.

2. Les urgences

Des patients arrivent avec une gravité de 1 à 5. Le plus grave passe en premier. Si deux patients ont la même gravité, celui qui est arrivé le premier passe d’abord. Utilisez un BinaryHeap de tuples et affichez l’ordre dans lequel les patients sont reçus. Patients : Mia (gravité 2, arrivée 1re), Leo (5, 2e), Sam (2, 3e), Zoe (4, 4e). Indice : les tuples se comparent champ par champ, exactement comme une struct dérivée. Essayez (severity, Reverse(arrival), name).

Voir la solution

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    // (gravité, Reverse(arrivée), nom)
    let mut waiting = BinaryHeap::new();
    waiting.push((2, Reverse(1), "Mia"));
    waiting.push((5, Reverse(2), "Leo"));
    waiting.push((2, Reverse(3), "Sam"));
    waiting.push((4, Reverse(4), "Zoe"));

    while let Some((severity, Reverse(arrival), name)) = waiting.pop() {
        println!("{name} (gravité {severity}, arrivée n°{arrival})");
    }
}

Sortie :

Leo (gravité 5, arrivée n°2)
Zoe (gravité 4, arrivée n°4)
Mia (gravité 2, arrivée n°1)
Sam (gravité 2, arrivée n°3)

▶ Essayez par vous-même

La gravité est comparée en premier, donc Leo passe d’abord. Mia et Sam sont à égalité de gravité, alors c’est Reverse(arrival) qui tranche, et la personne arrivée la première (Mia) l’emporte. Comme chaque numéro d’arrivée est différent, le nom n’est jamais nécessaire pour départager.

Récapitulatif

• Un Vec fait une piètre file : remove(0) décale tous les autres éléments. Une VecDeque est un tampon circulaire avec des push/pop rapides aux deux bouts.
• Utilisez VecDeque pour les files « premier arrivé, premier servi », les historiques des N derniers éléments et les fenêtres glissantes.
• Un BinaryHeap est un tas max : pop et peek donnent toujours le plus grand élément, sans tout trier.
• Enveloppez les valeurs dans std::cmp::Reverse pour obtenir un tas min (le plus petit d’abord).
• Les structs dans un tas ont besoin de Ord. Avec derive, les champs sont comparés de haut en bas : mettez donc la priorité en premier. Écrivez Ord à la main pour des départages sur mesure.
• .iter() sur un tas n’est pas trié. Retirez les éléments un par un, ou utilisez into_sorted_vec.

Petit quiz

Petit quiz

1. Pourquoi VecDeque::pop_front est-il plus rapide que Vec::remove(0) sur une longue liste ?

VecDeque stocke moins d'éléments Vec::remove(0) décale tous les autres éléments vers la gauche, alors qu'une VecDeque déplace juste sa position de début VecDeque trie d'abord ses éléments Il n'y a aucune différence

2. Vous ajoutez 4, 9 et 2 dans un BinaryHeap. Que renvoie le premier pop() ?

Some(4) Some(2) Some(9) None

3. Comment faire pour qu'un BinaryHeap vous donne la plus petite valeur d'abord ?

Envelopper chaque valeur dans std::cmp::Reverse Appeler .reverse() sur le tas Utiliser pop_front au lieu de pop C'est impossible ; utilisez un Vec

4. Une struct dérive Ord avec les champs name puis priority. Qu'est-ce qui décide de l'ordre dans un BinaryHeap ?

Seulement priority Rust choisit le champ le plus utile L'ordre dans lequel vous avez ajouté les éléments name d'abord ; priority ne sert qu'à départager les égalités

Score : 0 / 4

Pour aller plus loin

• std::collections — documentation de la bibliothèque standard (en anglais) : le guide officiel « quelle collection utiliser, et quand ? », avec un tableau des performances de chaque collection.
• VecDeque — documentation de la bibliothèque standard (en anglais) : toutes les méthodes, y compris rotate_left, range, retain et as_slices.
• BinaryHeap — documentation de la bibliothèque standard (en anglais) : toutes les méthodes du tas, avec des exemples de tas min avec Reverse et de peek_mut.
• Reverse — documentation de la bibliothèque standard (en anglais) : la toute petite enveloppe qui inverse n’importe quelle comparaison, avec des exemples de tri dans l’ordre inverse.
• Common Collections — The Rust Book (en anglais) : le chapitre du Book sur les vecteurs, les chaînes de caractères et les tables de hachage, les collections que vous utiliserez à côté de celles-ci.