VecDeque und BinaryHeap in Rust

Denk an die Schlange im Café. Neue Leute stellen sich hinten an, und die Barista bedient, wer vorne steht. Und jetzt denk an die Notaufnahme im Krankenhaus. Dort kommt der dringendste Fall zuerst dran, ganz egal, wann er angekommen ist. Beides sind „Warteschlangen“, aber sie folgen verschiedenen Regeln.

Rust hat für beides eine passende Collection. Eine VecDeque ist eine schnelle Warteschlange, bei der du an beiden Enden etwas hinzufügen und entfernen kannst. Ein BinaryHeap ist eine Prioritätswarteschlange (Priority Queue): Er gibt dir immer als Nächstes das größte (oder dringendste) Element. Vektoren kennst du schon, und auf der Seite zu HashSet hast du einen ersten kurzen Blick auf VecDeque geworfen. Diese Seite geht tiefer und nimmt BinaryHeap noch dazu.

Warum ein Vec eine schlechte Warteschlange ist

Du kannst einen Vec als Warteschlange benutzen. Hinten fügst du mit push hinzu, vorne nimmst du mit remove(0) weg. Das funktioniert. Das Problem ist, was dabei hinter den Kulissen passiert.

Ein Vec hält seine Elemente dicht hintereinander, beginnend bei Position 0. Wenn du das erste Element entfernst, muss jedes andere Element einen Platz nach links rutschen, um die Lücke zu füllen. Bei 3 Elementen merkt das niemand. Bei 100.000 Elementen verschiebt jedes einzelne remove(0) ganze 99.999 Werte. Genau das bedeutet „O(n)“: Der Aufwand wächst mit der Länge der Liste.

Eine VecDeque (sprich „Vec-Deck“, kurz für double-ended queue, also eine Warteschlange mit zwei Enden) löst das mit einem Ringpuffer (Ring Buffer). Stell dir einen runden Tisch mit nummerierten Plätzen vor und ein kleines Schild: „Hier beginnt die Schlange.“ Wenn die erste Person geht, steht niemand auf. Du schiebst nur das Schild einen Platz weiter. Kommt jemand Neues und der letzte Platz ist besetzt, setzt er sich auf Platz 0, falls der frei ist – einmal um den Tisch herum. Hinzufügen oder Entfernen an einem der Enden heißt also nur „Schild verschieben“ oder „einen Platz besetzen“. Das dauert immer gleich kurz, egal wie lang die Schlange ist. Das ist „O(1)“.

use std::collections::VecDeque;

fn main() {
    // Ein Vec als Warteschlange: geht, aber remove(0) schiebt alle nach links.
    let mut vec_line = vec!["Ana", "Ben", "Cai"];
    let served = vec_line.remove(0);
    println!("Vec bedient {served}, es warten noch: {:?}", vec_line);

    // Eine VecDeque: pop_front verschiebt nur ihre „Anfang“-Markierung.
    let mut deque_line = VecDeque::from(vec!["Ana", "Ben", "Cai"]);
    let served = deque_line.pop_front();
    println!("VecDeque bedient {:?}, es warten noch: {:?}", served, deque_line);
}

Ausgabe:

Vec bedient Ana, es warten noch: ["Ben", "Cai"]
VecDeque bedient Some("Ana"), es warten noch: ["Ben", "Cai"]

▶ Selbst ausprobieren

Das Ergebnis sieht gleich aus. Der Unterschied liegt in der Geschwindigkeit, und der zeigt sich erst, wenn die Schlange lang wird. Und noch etwas: pop_front gibt eine Option zurück. Ist die Schlange leer, bekommst du None statt eines Absturzes.

VecDeque-Grundlagen

VecDeque liegt in std::collections, du brauchst also eine use-Zeile. Danach lesen sich die Methoden fast wie Englisch: push (hinzufügen) oder pop (herausnehmen), vorne (front) oder hinten (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!("vorne: {:?}, hinten: {:?}", deque.front(), deque.back());
    println!("len: {}, leer: {}", 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!("entnommen: {:?} und {:?}, übrig: {:?}", first, last, deque);
}

Ausgabe:

[1, 2, 3]
vorne: Some(1), hinten: Some(3)
len: 3, leer: false
deque[1] = 2
get(9) = None
entnommen: Some(1) und Some(3), übrig: [2]

▶ Selbst ausprobieren

Mit front und back kannst du nachsehen, ohne etwas zu entfernen. Der Index-Zugriff mit deque[1] funktioniert genau wie bei einem Vec und löst eine Panic aus, wenn der Index zu groß ist. Nimm also get, wenn du dir nicht sicher bist.

Du kannst eine VecDeque auch aus einem Vec bauen, mit einer Schleife durchlaufen und wieder in einen Vec oder einen Slice verwandeln, wenn eine andere Funktion so etwas braucht:

use std::collections::VecDeque;

fn main() {
    let mut playlist = VecDeque::from(vec!["Intro", "Strophe", "Refrain"]);
    playlist.push_front("Einzähler");
    playlist.push_back("Outro");

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

    // Du brauchst einen normalen Slice? make_contiguous legt alles am Stück in den Speicher.
    let songs = playlist.make_contiguous();
    songs.sort();
    println!("sortiert: {:?}", songs);

    // Oder du machst das Ganze wieder zu einem Vec.
    let as_vec: Vec<&str> = playlist.into();
    println!("als Vec: {:?}", as_vec);
}

Ausgabe:

1. Einzähler
2. Intro
3. Strophe
4. Refrain
5. Outro
sortiert: ["Einzähler", "Intro", "Outro", "Refrain", "Strophe"]
als Vec: ["Einzähler", "Intro", "Outro", "Refrain", "Strophe"]

▶ Selbst ausprobieren

Wozu braucht man make_contiguous? Denk an den runden Tisch: Nachdem die Schlange ein paarmal herumgewandert ist, liegen die Elemente vielleicht in zwei getrennten Stücken im Speicher. make_contiguous räumt sie zu einem Stück zusammen und gibt dir einen normalen Slice zurück. Darauf kannst du dann Slice-Werkzeuge wie sort anwenden. Du brauchst das nicht oft, aber es ist gut zu wissen, dass es das gibt.

Echte Einsatzzwecke für VecDeque

Hier sind drei alltägliche Aufgaben, für die eine VecDeque perfekt passt.

Eine Aufgabenwarteschlange nach dem Prinzip „first in, first out“. Druckaufträge warten in einer Schlange. Neue Aufträge kommen nach hinten, der Drucker nimmt sie von vorne. Ein dringender Auftrag kann sich trotzdem mit push_front vordrängeln:

use std::collections::VecDeque;

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

    // Dringend! Dieser Auftrag springt ganz nach vorne.
    print_queue.push_front("bordkarte.pdf");

    while let Some(job) = print_queue.pop_front() {
        println!("Drucke {job} (noch {} in der Schlange)", print_queue.len());
    }
    println!("Alles erledigt. Warteschlange leer: {}", print_queue.is_empty());
}

Ausgabe:

Drucke bordkarte.pdf (noch 3 in der Schlange)
Drucke bericht.pdf (noch 2 in der Schlange)
Drucke foto.jpg (noch 1 in der Schlange)
Drucke rechnung.pdf (noch 0 in der Schlange)
Alles erledigt. Warteschlange leer: true

▶ Selbst ausprobieren

while let Some(job) = ...pop_front() ist die klassische Warteschlangen-Schleife. Sie läuft so lange, bis pop_front den Wert None zurückgibt – dann ist die Schlange leer. (Schau dir if let an, falls diese Form neu für dich ist.)

Ein Verlauf der „letzten N Einträge“. Ein Suchfeld merkt sich deine 3 letzten Suchen. Ist es voll, fällt die älteste vorne heraus:

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(); // die älteste Suche vergessen
    }
    recent.push_back(search.to_string());
}

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

    for search in ["rust buch", "vecdeque", "binary heap", "pizza in der nähe"] {
        remember(&mut recent, search);
        println!("{:?}", recent);
    }

    // Die neueste zuerst zeigen, so wie ein Suchfeld es tun würde.
    let newest_first: Vec<&String> = recent.iter().rev().collect();
    println!("neueste zuerst: {:?}", newest_first);
}

Ausgabe:

["rust buch"]
["rust buch", "vecdeque"]
["rust buch", "vecdeque", "binary heap"]
["vecdeque", "binary heap", "pizza in der nähe"]
neueste zuerst: ["pizza in der nähe", "binary heap", "vecdeque"]

▶ Selbst ausprobieren

Ein gleitender Durchschnitt. Ein Thermometer schickt jede Minute einen Messwert, und du willst den Durchschnitt der letzten 3. Jeder neue Messwert kommt hinten dazu, der älteste geht vorne raus. Weil du eine laufende Summe sum mitführst, musst du nie wieder das ganze Fenster zusammenzählen:

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(); // der älteste Messwert fällt raus
        }

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

Ausgabe:

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

▶ Selbst ausprobieren

Das unwrap() ist hier sicher: Wir nehmen nur dann etwas heraus, wenn das Fenster mehr als 3 Elemente hat. Leer kann es also nicht sein.

BinaryHeap: immer das Größte zuerst

Jetzt zur Notaufnahme. Manchmal ist dir egal, wer zuerst da war. Du willst immer wieder „gib mir als Nächstes das Wichtigste“, während ständig Neues dazukommt.

Du könntest alles in einen Vec stecken und ihn jedes Mal sortieren. Aber alles zu sortieren, nur um das oberste Element zu finden, ist eine Menge verschwendete Arbeit. Ein BinaryHeap hält seine Elemente nur grob geordnet – gerade so viel, dass das größte immer oben liegt. Ein Element hinzufügen oder das oberste herausnehmen ist günstig (O(log n), das wächst sehr langsam: etwa 17 Schritte bei 100.000 Elementen).

Der BinaryHeap von Rust ist ein Max-Heap: pop gibt dir immer den größten Wert. Hier sind die Gebote bei einer Auktion:

use std::collections::BinaryHeap;

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

    println!("höchstes Gebot: {:?}", bids.peek());
    println!("Anzahl Gebote: {}", bids.len());

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

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

Ausgabe:

höchstes Gebot: Some(450)
Anzahl Gebote: 4
nächstes: 450
nächstes: 300
nächstes: 120
nächstes: 80
sortiert: [1, 2, 3, 4, 5]

▶ Selbst ausprobieren

peek schaut sich das oberste Element an, ohne es zu entfernen. pop entfernt es. into_sorted_vec verbraucht den Heap und gibt dir einen Vec, sortiert vom kleinsten zum größten Wert. Wie bei VecDeque geben peek und pop beide eine Option zurück. Ein leerer Heap führt also nie zum Absturz.

Min-Heaps mit Reverse

Und wenn du das Kleinste zuerst willst? Den nächstgelegenen Lieferstopp, den billigsten Flug, die früheste Deadline. Dafür brauchst du keine andere Collection. Pack jeden Wert in std::cmp::Reverse. Das dreht den Vergleich einfach um: Was vorher das Größte war, ist jetzt das Kleinste.

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

fn main() {
    // Lieferstopps, nach Entfernung in km. Fahr immer zuerst zum nächsten.
    let mut stops = BinaryHeap::new();
    for km in [12, 3, 8, 5] {
        stops.push(Reverse(km));
    }

    if let Some(Reverse(closest)) = stops.peek() {
        println!("nächster Stopp: {closest} km");
    }

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

Ausgabe:

nächster Stopp: 3 km
fahre 3 km
fahre 5 km
fahre 8 km
fahre 12 km

▶ Selbst ausprobieren

Reverse(km) ist ein winziges Struct, das den Wert nur umhüllt. Das Pattern Some(Reverse(km)) packt beide Schichten auf einmal aus, sodass du die nackte Zahl zurückbekommst.

Eine Prioritätswarteschlange aus Structs

Echte Aufgaben sind nicht nur Zahlen. Sie haben einen Namen, eine Priorität, vielleicht eine Ankunftszeit. Damit du dein eigenes Struct in einen BinaryHeap stecken kannst, muss Rust wissen, wie man zwei davon vergleicht. Das Struct muss also Ord implementieren (siehe Wichtige Traits).

Am schnellsten geht das mit derive. Eines musst du dabei wissen: derive vergleicht die Felder von oben nach unten. Es vergleicht das erste Feld und schaut sich das zweite nur an, wenn die ersten gleich sind. Schreib das Feld, nach dem sortiert werden soll, also zuerst:

use std::collections::BinaryHeap;

// Die Reihenfolge der Felder zählt: derive vergleicht zuerst `priority`, dann `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: "E-Mail beantworten".to_string() });
    todo.push(Task { priority: 5, name: "Serverausfall beheben".to_string() });
    todo.push(Task { priority: 1, name: "Pflanzen gießen".to_string() });
    todo.push(Task { priority: 2, name: "Zahnarzt anrufen".to_string() });

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

Ausgabe:

[5] Serverausfall beheben
[2] Zahnarzt anrufen
[2] E-Mail beantworten
[1] Pflanzen gießen

▶ Selbst ausprobieren

Würdest du die beiden Felder vertauschen, sodass name zuerst kommt, dann würde der Heap die Aufgaben alphabetisch ordnen und die Priorität fast völlig ignorieren. Ein leichter Fehler – und ein stiller Bug.

Schau dir die beiden Aufgaben mit Priorität 2 an. Den Gleichstand hat name entschieden: „Zahnarzt anrufen“ gewinnt gegen „E-Mail beantworten“, weil „Z“ im Alphabet später kommt als „E“. Das ist vorhersehbar, aber vermutlich nicht das, was du willst – die E-Mail war ja zuerst da. Meistens soll bei Gleichstand die Aufgabe zuerst drankommen, die früher angekommen ist. Für so eine eigene Regel schreibst du Ord selbst:

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

#[derive(Debug, PartialEq, Eq)]
struct Job {
    priority: u8,
    id: u32, // Ankunftsreihenfolge: eine kleinere id kam früher an
    name: String,
}

impl Ord for Job {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority
            .cmp(&other.priority) // höhere Priorität gewinnt
            .then_with(|| other.id.cmp(&self.id)) // bei Gleichstand gewinnt die frühere id
    }
}

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: "E-Mail beantworten".to_string() });
    jobs.push(Job { priority: 5, id: 2, name: "Serverausfall beheben".to_string() });
    jobs.push(Job { priority: 1, id: 3, name: "Pflanzen gießen".to_string() });
    jobs.push(Job { priority: 2, id: 4, name: "Zahnarzt anrufen".to_string() });

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

Ausgabe:

[5] #2 Serverausfall beheben
[2] #1 E-Mail beantworten
[2] #4 Zahnarzt anrufen
[1] #3 Pflanzen gießen

▶ Selbst ausprobieren

Jetzt kommt die E-Mail (#1) vor dem Zahnarzt (#4) dran. Der Trick steckt in then_with: Sind die Prioritäten gleich, vergleichst du die ids rückwärts (other.id mit self.id). Dadurch zählt die kleinere id als „größer“ und kommt im Max-Heap zuerst heraus. Keine Sorge, wenn das einen Moment dauert, bis es sitzt. Den Vergleich umdrehen – genau das macht Reverse für dich, hier nur von Hand ausgeschrieben. Der PartialOrd-Block ist immer derselbe Standard-Code: Er ruft einfach dein cmp auf.

Ein echter Algorithmus: die Top 3

Angenommen, du hast eine riesige Liste mit Spielpunkten und willst nur die besten 3. Die ganze Liste zu sortieren funktioniert. Es gibt aber einen eleganten Trick, bei dem du immer nur 3 Elemente aufbewahrst.

Nimm einen Min-Heap der Größe 3. Leg jede Punktzahl hinein. Sobald der Heap 4 Elemente hat, nimmst du eines heraus. Weil es ein Min-Heap ist, wirfst du dabei immer das kleinste weg. Am Ende bleiben nur die 3 besten übrig.

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(); // ein Min-Heap: die kleinste Punktzahl liegt oben

    for score in scores {
        top.push(Reverse(score));
        if top.len() > 3 {
            top.pop(); // vier sind einer zu viel: die kleinste fliegt raus
        }
    }

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

Ausgabe:

Top 3: [99, 95, 91]

▶ Selbst ausprobieren

Ein netter Bonus: into_sorted_vec sortiert die Reverse-Werte vom „kleinsten“ zum „größten“. Für die echten Punktzahlen heißt das: vom größten zum kleinsten. Die beste Punktzahl kommt also zuerst, ganz ohne zusätzliches Sortieren. Dieses Muster funktioniert auch für eine Liste mit einer Million Punktzahlen, und es hält dabei nie mehr als 4 im Speicher.

Was soll ich nehmen?

Hier ist ein Spickzettel. „Schnell“ heißt: Die Zeit bleibt ungefähr gleich, egal wie groß die Collection wird. „Langsam“ heißt: Sie wächst mit der Größe.

Collection	Stark bei	Hinzufügen	Vorne / oben herausnehmen	Beliebiges Element finden
Vec<T>	Eine Liste, die du nach Position liest; ein Stack	Schnell am Ende	Langsam (remove(0) verschiebt alles)	Langsam (jedes Element anschauen)
VecDeque<T>	Warteschlangen: an beiden Enden hinzufügen und entfernen	Schnell an beiden Enden	Schnell an beiden Enden	Langsam (jedes Element anschauen)
BinaryHeap<T>	„Gib mir als Nächstes das Größte / Dringendste“	Ziemlich schnell (O(log n))	Ziemlich schnell: immer das größte	Langsam, und keine sortierte Reihenfolge
BTreeSet<T>	Eindeutige Werte, immer sortiert	Ziemlich schnell (O(log n))	Ziemlich schnell: kleinstes und größtes	Ziemlich schnell (O(log n))

Im Zweifel fang mit einem Vec an. Greif zu einer VecDeque, wenn du Dinge vorne wegnimmst. Greif zu einem BinaryHeap, wenn du immer wieder fragst: „Was ist jetzt am wichtigsten?“ Nimm ein BTreeSet, wenn du sortierte, eindeutige Werte brauchst und Elemente nachschlagen willst, statt nur das oberste zu nehmen.

Häufige Fehler

Erwarten, dass .iter() auf einem BinaryHeap sortiert ist. Ein Heap ist nur grob geordnet. Das größte Element steht vorne, aber der Rest liegt in einem Durcheinander, das dem Heap nützt, nicht dir:

use std::collections::BinaryHeap;

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

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

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

Ausgabe:

iter:     [9, 8, 2, 5, 3, 1]
sortiert: [1, 2, 3, 5, 8, 9]
entnommen: 9 8 5 3 2 1

▶ Selbst ausprobieren

Dasselbe gilt, wenn du einen Heap mit {:?} ausgibst: Du siehst das interne Durcheinander. Brauchst du die Elemente in Reihenfolge, dann nimm sie mit pop einzeln heraus oder ruf into_sorted_vec auf.

Ein Struct ohne Ord in einen BinaryHeap stecken. Der Heap muss Elemente vergleichen, um zu wissen, welches nach oben gehört. Kann dein Struct nicht verglichen werden, hält Rust dich auf:

use std::collections::BinaryHeap;

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

fn main() {
    let mut tickets = BinaryHeap::new();
    tickets.push(Ticket { urgency: 3, title: "Login kaputt".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 kaputt".to_string() });
   |             ^^^^ the trait `Ord` is not implemented for `Ticket`
   |
help: consider annotating `Ticket` with `#[derive(Ord)]`

Der Compiler sagt: Der Trait Ord ist für Ticket nicht implementiert, und er schlägt vor, ihn mit #[derive(Ord)] abzuleiten. Die Lösung: Schreib #[derive(PartialEq, Eq, PartialOrd, Ord)] über das Struct (Ord braucht auch die anderen drei), mit urgency als erstem Feld. Oder schreib Ord von Hand, wie im Job-Beispiel oben.

Übungen

1. Reihum spielen

Drei Freunde, Ana, Ben und Cai, spielen reihum ein Brettspiel. Steck sie in eine VecDeque und gib aus, wer in den Zügen 1 bis 5 dran ist. Nach jedem Zug stellt sich der Spieler wieder hinten an. Tipp: Hol den Spieler mit pop_front heraus, gib ihn aus und häng ihn mit push_back wieder hinten an.

Lösung anzeigen

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!("Zug {turn}: {player}");
        players.push_back(player); // zurück ans Ende der Schlange
    }
}

Ausgabe:

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

▶ Selbst ausprobieren

Vorne und hinten sind bei einer VecDeque beide schnell. Die Schlange weiterzudrehen kostet also fast nichts, egal wie viele Spieler mitmachen.

2. Die Notaufnahme

Patienten kommen mit einem Schweregrad von 1 bis 5 an. Der schwerste Fall kommt zuerst dran. Haben zwei Patienten denselben Schweregrad, kommt dran, wer früher da war. Nimm einen BinaryHeap aus Tupeln und gib aus, in welcher Reihenfolge die Patienten behandelt werden. Patienten: Mia (Schweregrad 2, als 1. angekommen), Leo (5, als 2.), Sam (2, als 3.), Zoe (4, als 4.). Tipp: Tupel werden Feld für Feld verglichen, genau wie ein Struct mit derive. Probier (severity, Reverse(arrival), name).

Lösung anzeigen

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} (Schweregrad {severity}, Ankunft #{arrival})");
    }
}

Ausgabe:

Leo (Schweregrad 5, Ankunft #2)
Zoe (Schweregrad 4, Ankunft #4)
Mia (Schweregrad 2, Ankunft #1)
Sam (Schweregrad 2, Ankunft #3)

▶ Selbst ausprobieren

Der Schweregrad wird zuerst verglichen, deshalb ist Leo als Erster dran. Mia und Sam haben denselben Schweregrad, also entscheidet Reverse(arrival), und wer früher kam (Mia), gewinnt. Weil jede Ankunftsnummer anders ist, wird der Name nie gebraucht, um einen Gleichstand aufzulösen.

Zusammenfassung

• Ein Vec ist eine schlechte Warteschlange: remove(0) verschiebt alle anderen Elemente. Eine VecDeque ist ein Ringpuffer mit schnellem push/pop an beiden Enden.
• Nimm VecDeque für Warteschlangen nach „first in, first out“, für Verläufe der „letzten N Einträge“ und für gleitende Fenster.
• Ein BinaryHeap ist ein Max-Heap: pop und peek liefern immer das größte Element, ohne alles zu sortieren.
• Pack Werte in std::cmp::Reverse, um einen Min-Heap zu bekommen (das Kleinste zuerst).
• Structs in einem Heap brauchen Ord. Mit derive werden die Felder von oben nach unten verglichen, schreib die Priorität also zuerst. Für eigene Regeln bei Gleichstand schreibst du Ord von Hand.
• .iter() auf einem Heap ist nicht sortiert. Nimm die Elemente einzeln mit pop heraus oder benutze into_sorted_vec.

Kurzer Check

Kurzer Check

1. Warum ist VecDeque::pop_front bei einer langen Liste schneller als Vec::remove(0)?

VecDeque speichert weniger Elemente Vec::remove(0) schiebt alle anderen Elemente nach links, eine VecDeque verschiebt nur ihre Anfangsposition VecDeque sortiert ihre Elemente vorher Es gibt keinen Unterschied

2. Du legst 4, 9 und 2 in einen BinaryHeap. Was gibt das erste pop() zurück?

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

3. Wie bringst du einen BinaryHeap dazu, dir zuerst den kleinsten Wert zu geben?

Jeden Wert in std::cmp::Reverse packen .reverse() auf dem Heap aufrufen pop_front statt pop benutzen Gar nicht; nimm einen Vec

4. Ein Struct leitet Ord mit derive ab, mit den Feldern name und dann priority. Was bestimmt die Reihenfolge in einem BinaryHeap?

Nur priority Rust wählt das nützlichste Feld Die Reihenfolge, in der du die Elemente hinzugefügt hast Zuerst name; priority entscheidet nur bei Gleichstand

Punkte: 0 / 4

Weiterlesen

• std::collections – Doku der Standardbibliothek (auf Englisch): der offizielle Leitfaden „Wann sollte ich welche Collection nehmen?“, mit einer Geschwindigkeitstabelle für jede Collection.
• VecDeque – Doku der Standardbibliothek (auf Englisch): alle Methoden, auch rotate_left, range, retain und as_slices.
• BinaryHeap – Doku der Standardbibliothek (auf Englisch): alle Heap-Methoden, dazu Beispiele für Min-Heaps mit Reverse und für peek_mut.
• Reverse – Doku der Standardbibliothek (auf Englisch): der winzige Wrapper, der jeden Vergleich umdreht, mit Beispielen zum Sortieren in umgekehrter Reihenfolge.
• Allgemeine Kollektionen – Das Rust-Buch: das Kapitel des Buchs über Vektoren, Zeichenketten und Hashtabellen – die Collections, die du neben diesen hier benutzen wirst.