VecDeque e BinaryHeap in Rust

Pensa alla fila al bar. Chi arriva si mette in fondo, e il barista serve chi è davanti. Ora pensa al pronto soccorso. Lì passa per primo il paziente più grave, indipendentemente da quando è arrivato. Sono entrambe «file d’attesa», ma seguono regole diverse.

Rust ha una collezione per ciascuna. Un VecDeque è una fila veloce in cui puoi aggiungere e togliere da entrambe le estremità. Un BinaryHeap è una coda di priorità: ti dà sempre come prossimo l’elemento più grande (o più urgente). Conosci già i Vettori, e la pagina su HashSet ti ha fatto dare una prima occhiata a VecDeque. Questa pagina va più a fondo e aggiunge BinaryHeap.

Perché un Vec è una pessima coda

Puoi usare un Vec come coda. Aggiungi con push, prendi dall’inizio con remove(0). Funziona. Il problema è quello che succede dietro le quinte.

Un Vec tiene i suoi elementi compatti, uno dopo l’altro, a partire dalla posizione 0. Quando togli il primo, tutti gli altri devono scivolare di un posto a sinistra per riempire il buco. Con 3 elementi nessuno se ne accorge. Con 100.000 elementi, ogni singola remove(0) sposta 99.999 valori. È questo che significa «O(n)»: il lavoro cresce con la dimensione della lista.

Un VecDeque (si legge «vec deck», abbreviazione di double-ended queue, coda a doppia estremità) risolve il problema con un buffer circolare (ring buffer). Immagina un tavolo rotondo con i posti numerati e un cartellino che dice «la fila parte da qui». Quando la prima persona se ne va, nessuno si alza: sposti solo il cartellino al posto successivo. Quando arriva qualcuno di nuovo e l’ultimo posto è occupato, si siede al posto 0 se è libero, facendo il giro del tavolo. Aggiungere o togliere a una delle due estremità vuol dire solo «sposta il cartellino» o «occupa un posto», quindi richiede sempre lo stesso pochissimo tempo, per quanto lunga sia la fila. È «O(1)».

use std::collections::VecDeque;

fn main() {
    // Un Vec usato come coda: funziona, ma remove(0) sposta tutti a sinistra.
    let mut vec_line = vec!["Ana", "Ben", "Cai"];
    let served = vec_line.remove(0);
    println!("Il Vec ha servito {served}, ancora in attesa: {:?}", vec_line);

    // Un VecDeque: pop_front sposta solo il suo segnaposto di «inizio».
    let mut deque_line = VecDeque::from(vec!["Ana", "Ben", "Cai"]);
    let served = deque_line.pop_front();
    println!("Il VecDeque ha servito {:?}, ancora in attesa: {:?}", served, deque_line);
}

Output:

Il Vec ha servito Ana, ancora in attesa: ["Ben", "Cai"]
Il VecDeque ha servito Some("Ana"), ancora in attesa: ["Ben", "Cai"]

▶ Provalo tu

Il risultato sembra lo stesso. La differenza è la velocità, e si vede solo quando la fila diventa lunga. Nota anche un’altra cosa: pop_front restituisce un Option. Se la fila è vuota ottieni None, invece di un crash.

Le basi di VecDeque

VecDeque si trova in std::collections, quindi ti serve una riga use. Dopodiché i metodi si leggono quasi come frasi in inglese: push o pop, davanti (front) o dietro (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!("davanti: {:?}, dietro: {:?}", deque.front(), deque.back());
    println!("lunghezza: {}, vuoto: {}", 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!("estratti {:?} e {:?}, rimasti: {:?}", first, last, deque);
}

Output:

[1, 2, 3]
davanti: Some(1), dietro: Some(3)
lunghezza: 3, vuoto: false
deque[1] = 2
get(9) = None
estratti Some(1) e Some(3), rimasti: [2]

▶ Provalo tu

front e back ti permettono di guardare senza togliere niente. L’indicizzazione con deque[1] funziona proprio come in un Vec, e va in panic se l’indice è troppo grande, quindi usa get quando non sei sicuro.

Puoi anche costruire un VecDeque a partire da un Vec, scorrerlo e trasformarlo di nuovo in un Vec o in una slice quando un’altra funzione ne ha bisogno:

use std::collections::VecDeque;

fn main() {
    let mut playlist = VecDeque::from(vec!["Intro", "Verse", "Chorus"]);
    playlist.push_front("Count-in");
    playlist.push_back("Outro");

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

    // Ti serve una slice normale? make_contiguous mette tutto in fila in memoria.
    let songs = playlist.make_contiguous();
    songs.sort();
    println!("ordinate: {:?}", songs);

    // Oppure trasforma tutto di nuovo in un Vec.
    let as_vec: Vec<&str> = playlist.into();
    println!("come Vec: {:?}", as_vec);
}

Output:

1. Count-in
2. Intro
3. Verse
4. Chorus
5. Outro
ordinate: ["Chorus", "Count-in", "Intro", "Outro", "Verse"]
come Vec: ["Chorus", "Count-in", "Intro", "Outro", "Verse"]

▶ Provalo tu

I nomi delle parti del brano restano in inglese, come si usano in musica (e così l’ordine alfabetico non cambia). Perché serve make_contiguous? Ricorda il tavolo rotondo: dopo qualche giro, gli elementi potrebbero trovarsi in due pezzi di memoria separati. make_contiguous li riordina in un pezzo solo e ti dà una normale slice, così puoi usare gli strumenti delle slice come sort. Non ti servirà spesso, ma è bene sapere che esiste.

Usi reali di VecDeque

Ecco tre lavori di tutti i giorni in cui un VecDeque è perfetto.

Una coda di task in cui il primo che entra è il primo che esce. I lavori di stampa aspettano in fila. I nuovi vanno in fondo, la stampante prende dall’inizio. Un lavoro urgente può comunque passare avanti con push_front:

use std::collections::VecDeque;

fn main() {
    let mut print_queue = VecDeque::new();
    print_queue.push_back("relazione.pdf");
    print_queue.push_back("foto.jpg");
    print_queue.push_back("fattura.pdf");

    // Urgente! Questo salta in testa alla fila.
    print_queue.push_front("carta-imbarco.pdf");

    while let Some(job) = print_queue.pop_front() {
        println!("Stampo {job} ({} ancora in attesa)", print_queue.len());
    }
    println!("Tutto fatto. Coda vuota: {}", print_queue.is_empty());
}

Output:

Stampo carta-imbarco.pdf (3 ancora in attesa)
Stampo relazione.pdf (2 ancora in attesa)
Stampo foto.jpg (1 ancora in attesa)
Stampo fattura.pdf (0 ancora in attesa)
Tutto fatto. Coda vuota: true

▶ Provalo tu

while let Some(job) = ...pop_front() è il classico ciclo di una coda. Va avanti finché pop_front non restituisce None, cioè finché la fila non è vuota. (Vedi if let se questa forma ti è nuova.)

Una cronologia degli «ultimi N elementi». Una casella di ricerca che ricorda le tue 3 ricerche più recenti. Quando è piena, la più vecchia cade fuori dall’inizio:

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(); // dimentica la ricerca più vecchia
    }
    recent.push_back(search.to_string());
}

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

    for search in ["libro rust", "vecdeque", "binary heap", "pizzeria qui vicino"] {
        remember(&mut recent, search);
        println!("{:?}", recent);
    }

    // Mostra prima le più recenti, come farebbe una casella di ricerca.
    let newest_first: Vec<&String> = recent.iter().rev().collect();
    println!("prima le più recenti: {:?}", newest_first);
}

Output:

["libro rust"]
["libro rust", "vecdeque"]
["libro rust", "vecdeque", "binary heap"]
["vecdeque", "binary heap", "pizzeria qui vicino"]
prima le più recenti: ["pizzeria qui vicino", "binary heap", "vecdeque"]

▶ Provalo tu

Una media su una finestra scorrevole. Un termometro invia una lettura ogni minuto, e tu vuoi la media delle ultime 3. Ogni nuova lettura entra in fondo, e la più vecchia esce dall’inizio. Tenere una sum aggiornata significa che non devi mai risommare tutta la finestra:

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 lettura più vecchia esce
        }

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

Output:

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

▶ Provalo tu

Qui unwrap() è sicuro: facciamo pop solo quando la finestra ha più di 3 elementi, quindi non può essere vuota.

BinaryHeap: sempre il più grande come prossimo

Ora il pronto soccorso. A volte non ti interessa chi è arrivato prima. Vuoi «dammi la cosa più importante adesso», ancora e ancora, mentre continuano ad arrivare cose nuove.

Potresti mettere tutto in un Vec e ordinarlo ogni volta. Ma ordinare tutto solo per trovare l’elemento in cima è un sacco di lavoro sprecato. Un BinaryHeap tiene i suoi elementi organizzati solo a grandi linee, quanto basta perché il più grande sia sempre in cima. Aggiungere un elemento o prendere quello in cima costa poco (O(log n), che cresce molto lentamente: circa 17 passi per 100.000 elementi).

Il BinaryHeap di Rust è un max-heap: pop ti dà sempre il valore più grande. Ecco le offerte di un’asta:

use std::collections::BinaryHeap;

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

    println!("offerta più alta: {:?}", bids.peek());
    println!("numero di offerte: {}", bids.len());

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

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

Output:

offerta più alta: Some(450)
numero di offerte: 4
prossima: 450
prossima: 300
prossima: 120
prossima: 80
ordinati: [1, 2, 3, 4, 5]

▶ Provalo tu

peek guarda l’elemento in cima senza toglierlo. pop lo toglie. into_sorted_vec consuma l’heap e ti dà un Vec ordinato dal più piccolo al più grande. Come per VecDeque, sia peek sia pop restituiscono un Option, quindi un heap vuoto non causa mai un crash.

Min-heap con Reverse

E se vuoi prima il più piccolo? La fermata di consegna più vicina, il volo più economico, la scadenza più vicina. Non ti serve un’altra collezione. Avvolgi ogni valore in std::cmp::Reverse, che semplicemente rovescia il confronto: quello che era il più grande ora è il più piccolo.

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

fn main() {
    // Fermate di consegna, per distanza in km. Vai sempre alla più vicina.
    let mut stops = BinaryHeap::new();
    for km in [12, 3, 8, 5] {
        stops.push(Reverse(km));
    }

    if let Some(Reverse(closest)) = stops.peek() {
        println!("fermata più vicina: {closest} km");
    }

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

Output:

fermata più vicina: 3 km
guida per 3 km
guida per 5 km
guida per 8 km
guida per 12 km

▶ Provalo tu

Reverse(km) è una piccolissima struct che fa da involucro. Il pattern Some(Reverse(km)) toglie entrambi gli strati in un colpo, così ti ritrovi il semplice numero.

Una coda di priorità di struct

I task veri non sono solo numeri. Hanno un nome, una priorità, magari un orario di arrivo. Per mettere una tua struct in un BinaryHeap, Rust deve sapere come confrontarne due, il che significa che la struct deve implementare Ord (vedi Trait comuni).

Il modo più rapido è derive. Una cosa da sapere: derive confronta i campi dall’alto verso il basso. Confronta il primo campo, e guarda il secondo solo se i primi sono uguali. Quindi metti per primo il campo in base a cui vuoi ordinare:

use std::collections::BinaryHeap;

// L'ordine dei campi conta: derive confronta prima `priority`, poi `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: "prenota il dentista".to_string() });
    todo.push(Task { priority: 5, name: "risolvi il guasto".to_string() });
    todo.push(Task { priority: 1, name: "annaffia le piante".to_string() });
    todo.push(Task { priority: 2, name: "rispondi alle email".to_string() });

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

Output:

[5] risolvi il guasto
[2] rispondi alle email
[2] prenota il dentista
[1] annaffia le piante

▶ Provalo tu

Se scambiassi i due campi mettendo name per primo, l’heap ordinerebbe i task in ordine alfabetico e ignorerebbe quasi del tutto la priorità. Errore facile, bug silenzioso.

Guarda i due task con priorità 2. «prenota il dentista» è arrivato per primo, ma «rispondi alle email» è uscito per primo. La parità è stata risolta da name, e «rispondi» batte «prenota» perché viene dopo in ordine alfabetico. È prevedibile, ma probabilmente non è quello che vuoi. Di solito, a parità, dovrebbe passare per primo il task arrivato prima. Per una regola personalizzata come questa, scrivi Ord a mano:

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

#[derive(Debug, PartialEq, Eq)]
struct Job {
    priority: u8,
    id: u32, // ordine di arrivo: un id più basso è arrivato prima
    name: String,
}

impl Ord for Job {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority
            .cmp(&other.priority) // vince la priorità più alta
            .then_with(|| other.id.cmp(&self.id)) // a parità, vince l'id più basso
    }
}

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: "prenota il dentista".to_string() });
    jobs.push(Job { priority: 5, id: 2, name: "risolvi il guasto".to_string() });
    jobs.push(Job { priority: 1, id: 3, name: "annaffia le piante".to_string() });
    jobs.push(Job { priority: 2, id: 4, name: "rispondi alle email".to_string() });

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

Output:

[5] #2 risolvi il guasto
[2] #1 prenota il dentista
[2] #4 rispondi alle email
[1] #3 annaffia le piante

▶ Provalo tu

Il trucco sta in then_with: se le priorità sono uguali, confronta gli id al contrario (other.id con self.id). Così l’id più piccolo conta come «più grande», ed esce per primo dal max-heap. Non preoccuparti se ti ci vuole un minuto per digerirlo. Rovesciare il confronto è esattamente quello che fa Reverse per te, solo scritto a mano. Il blocco PartialOrd è sempre lo stesso codice di contorno: chiama semplicemente la tua cmp.

Un algoritmo vero: i 3 punteggi migliori

Supponi di avere una lista enorme di punteggi di un gioco e di volere solo i 3 migliori. Ordinare tutta la lista funziona, ma c’è un trucco elegante che tiene in memoria solo 3 elementi alla volta.

Usa un min-heap di dimensione 3. Inserisci ogni punteggio. Quando l’heap ha 4 elementi, fai un pop. Visto che è un min-heap, quello che butti via è il più piccolo. Alla fine restano solo i 3 migliori.

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 min-heap: in cima c'è il punteggio più basso

    for score in scores {
        top.push(Reverse(score));
        if top.len() > 3 {
            top.pop(); // quattro sono uno di troppo: scarta il più piccolo
        }
    }

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

Output:

i 3 migliori: [99, 95, 91]

▶ Provalo tu

Un bel bonus: into_sorted_vec ordina i valori Reverse dal «più piccolo» al «più grande», che per i punteggi veri significa dal più grande al più piccolo. Quindi il punteggio migliore esce per primo, senza ordinamenti in più. Questo schema funziona con una lista di un milione di punteggi tenendone in memoria al massimo 4.

Quale usare?

Ecco un promemoria. «Veloce» significa che il tempo resta più o meno lo stesso per quanto cresca la collezione. «Lento» significa che cresce con la dimensione.

Collezione	Ottima per	Inserire	Prendere dall’inizio / dalla cima	Trovare un elemento qualsiasi
Vec<T>	Una lista letta per posizione; una pila	Veloce in fondo	Lento (remove(0) sposta tutto)	Lento (guarda ogni elemento)
VecDeque<T>	Code: aggiungere e togliere da entrambe le estremità	Veloce a entrambe le estremità	Veloce a entrambe le estremità	Lento (guarda ogni elemento)
BinaryHeap<T>	«Dammi il più grande / il più urgente adesso»	Abbastanza veloce (O(log n))	Abbastanza veloce: sempre il più grande	Lento, e senza ordine
BTreeSet<T>	Valori unici, sempre tenuti in ordine	Abbastanza veloce (O(log n))	Abbastanza veloce: il più piccolo e il più grande	Abbastanza veloce (O(log n))

Nel dubbio, parti con un Vec. Passa a un VecDeque quando prendi le cose dall’inizio. Passa a un BinaryHeap quando continui a chiederti «qual è la cosa più importante adesso?». Usa un BTreeSet quando ti servono valori unici e ordinati e vuoi cercare elementi, non solo prendere quello in cima.

Errori comuni

Aspettarsi che .iter() su un BinaryHeap sia ordinato. Un heap è ordinato solo a grandi linee. L’elemento più grande è il primo, ma gli altri sono in un ordine confuso che è utile all’heap, non a te:

use std::collections::BinaryHeap;

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

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

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

Output:

iter:     [9, 8, 2, 5, 3, 1]
ordinati: [1, 2, 3, 5, 8, 9]
estratti: 9 8 5 3 2 1

▶ Provalo tu

Lo stesso vale se stampi un heap con {:?}: vedrai il disordine interno. Se ti servono gli elementi in ordine, estraili con pop uno per uno o chiama into_sorted_vec.

Mettere in un BinaryHeap una struct senza Ord. L’heap deve confrontare gli elementi per sapere quale va in cima. Se la tua struct non si può confrontare, Rust ti ferma:

use std::collections::BinaryHeap;

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

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

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

Il compilatore dice che Ticket non implementa Ord e suggerisce di aggiungere #[derive(Ord)] (il titolo del ticket resta in inglese, perché compare anche nel messaggio di errore). La soluzione è aggiungere #[derive(PartialEq, Eq, PartialOrd, Ord)] sopra la struct (Ord ha bisogno anche degli altri tre), con urgency come primo campo. Oppure scrivere Ord a mano, come nell’esempio di Job qui sopra.

Pratica

1. A turno

Tre amici, Ana, Ben e Cai, fanno a turno in un gioco da tavolo. Mettili in un VecDeque e stampa chi gioca nei turni da 1 a 5. Dopo ogni turno, il giocatore torna in fondo alla fila. Suggerimento: prendi il giocatore con pop_front, stampalo, poi rimetti lo stesso giocatore con push_back.

Mostra la soluzione

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!("Turno {turn}: {player}");
        players.push_back(player); // di nuovo in fondo alla fila
    }
}

Output:

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

▶ Provalo tu

In un VecDeque sia l’inizio sia la fine sono veloci, quindi far ruotare la fila non costa quasi niente, per quanti giocatori ci siano.

2. Il pronto soccorso

I pazienti arrivano con una gravità da 1 a 5. Il più grave passa per primo. Se due pazienti hanno la stessa gravità, passa per primo chi è arrivato prima. Usa un BinaryHeap di tuple e stampa l’ordine in cui vengono visitati i pazienti. Pazienti: Mia (gravità 2, arrivata per 1ª), Leo (5, 2º), Sam (2, 3º), Zoe (4, 4ª). Suggerimento: le tuple si confrontano campo per campo, proprio come una struct con derive. Prova (severity, Reverse(arrival), name).

Mostra la soluzione

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

fn main() {
    // (severity, Reverse(arrival), name)
    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}, arrivo n. {arrival})");
    }
}

Output:

Leo (gravità 5, arrivo n. 2)
Zoe (gravità 4, arrivo n. 4)
Mia (gravità 2, arrivo n. 1)
Sam (gravità 2, arrivo n. 3)

▶ Provalo tu

La gravità viene confrontata per prima, quindi Leo passa per primo. Mia e Sam sono pari per gravità, quindi decide Reverse(arrival), e vince chi è arrivata prima (Mia). Visto che ogni numero di arrivo è diverso, il nome non serve mai per risolvere una parità.

Riepilogo

• Un Vec è una pessima coda: remove(0) sposta tutti gli altri elementi. Un VecDeque è un buffer circolare con push/pop veloci a entrambe le estremità.
• Usa VecDeque per code in cui il primo che entra è il primo che esce, per cronologie degli «ultimi N elementi» e per finestre scorrevoli.
• Un BinaryHeap è un max-heap: pop e peek danno sempre l’elemento più grande, senza ordinare tutto.
• Avvolgi i valori in std::cmp::Reverse per ottenere un min-heap (prima il più piccolo).
• Le struct in un heap hanno bisogno di Ord. Con derive i campi si confrontano dall’alto verso il basso, quindi metti per prima la priorità. Scrivi Ord a mano per regole di parità personalizzate.
• .iter() su un heap non è ordinato. Estrai gli elementi uno per uno, o usa into_sorted_vec.

Verifica veloce

Verifica veloce

1. Perché su una lista lunga VecDeque::pop_front è più veloce di Vec::remove(0)?

VecDeque salva meno elementi Vec::remove(0) sposta a sinistra tutti gli altri elementi, mentre un VecDeque sposta solo la sua posizione di inizio VecDeque prima ordina i suoi elementi Non c'è differenza

2. Inserisci 4, 9 e 2 in un BinaryHeap. Che cosa restituisce il primo pop()?

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

3. Come fai in modo che un BinaryHeap ti dia prima il valore più piccolo?

Avvolgi ogni valore in std::cmp::Reverse Chiami .reverse() sull'heap Usi pop_front invece di pop Non puoi; usa un Vec

4. Una struct fa derive di Ord con i campi name e poi priority. Che cosa decide l'ordine in un BinaryHeap?

Solo priority Rust sceglie il campo più utile L'ordine in cui hai inserito gli elementi Prima name; priority risolve solo le parità

Punteggio: 0 / 4

Per approfondire

• std::collections — documentazione della libreria standard (in inglese): la guida ufficiale «quale collezione usare e quando», con una tabella delle velocità di ogni collezione.
• VecDeque — documentazione della libreria standard (in inglese): tutti i metodi, compresi rotate_left, range, retain e as_slices.
• BinaryHeap — documentazione della libreria standard (in inglese): tutti i metodi dell’heap, più esempi di min-heap con Reverse e di peek_mut.
• Reverse — documentazione della libreria standard (in inglese): il piccolo involucro che rovescia qualsiasi confronto, con esempi di ordinamento al contrario.
• Common Collections — The Rust Book (in inglese): il capitolo del Book su vettori, stringhe e hash map, le collezioni che userai insieme a queste.