VecDeque и BinaryHeap в Rust

Вспомни очередь в кофейне. Новые люди встают в конец, а бариста обслуживает того, кто стоит первым. А теперь вспомни приёмный покой в больнице. Там первым идёт самый тяжёлый пациент, неважно, когда он пришёл. И то и другое — «очереди», но правила у них разные.

Для каждой из них в Rust есть своя коллекция. VecDeque — быстрая очередь, в которую можно добавлять и из которой можно удалять с обоих концов. BinaryHeap — очередь с приоритетом (priority queue): она всегда отдаёт следующим самый большой (или самый срочный) элемент. Ты уже знаешь векторы, а в уроке HashSet и BTreeMap мельком познакомился с VecDeque. Здесь мы разберём его подробнее и добавим BinaryHeap.

Почему Vec — плохая очередь

Использовать Vec как очередь можно. Добавляешь через push, забираешь спереди через remove(0). Работает. Проблема в том, что происходит за кулисами.

Vec хранит элементы плотно, начиная с позиции 0. Когда ты удаляешь первый элемент, все остальные должны сдвинуться на шаг влево, чтобы закрыть дыру. При трёх элементах никто этого не заметит. При 100 000 элементов каждый remove(0) двигает 99 999 значений. Это и есть «O(n)»: работа растёт вместе с размером списка.

VecDeque (произносится «век-дек», сокращение от double-ended queue — двусторонняя очередь) решает это с помощью кольцевого буфера (ring buffer). Представь круглый стол с пронумерованными местами и табличку «очередь начинается здесь». Когда первый человек уходит, никто не встаёт с места. Ты просто переставляешь табличку на следующее место. Когда приходит новый человек, а последнее место занято, он садится на место 0, если оно свободно, — обходит стол по кругу. Добавить или убрать с любого конца — это просто «переставить табличку» или «занять одно место», поэтому времени это занимает одинаково мало, какой бы длинной ни была очередь. Это «O(1)».

use std::collections::VecDeque;

fn main() {
    // Vec в роли очереди: работает, но remove(0) сдвигает всех влево.
    let mut vec_line = vec!["Аня", "Бен", "Кай"];
    let served = vec_line.remove(0);
    println!("Vec обслужил: {served}, ещё ждут: {:?}", vec_line);

    // VecDeque: pop_front просто передвигает метку «начала».
    let mut deque_line = VecDeque::from(vec!["Аня", "Бен", "Кай"]);
    let served = deque_line.pop_front();
    println!("VecDeque обслужил: {:?}, ещё ждут: {:?}", served, deque_line);
}

Вывод:

Vec обслужил: Аня, ещё ждут: ["Бен", "Кай"]
VecDeque обслужил: Some("Аня"), ещё ждут: ["Бен", "Кай"]

▶ Попробуй сам

Результат выглядит одинаково. Разница — в скорости, и видна она только на длинной очереди. Заметь ещё одно: pop_front возвращает Option. Если очередь пуста, ты получишь None, а не падение программы.

Основы VecDeque

VecDeque лежит в std::collections, поэтому нужна строка use. Дальше методы читаются почти как обычный английский: push или pop, front (спереди) или 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!("спереди: {:?}, сзади: {:?}", deque.front(), deque.back());
    println!("длина: {}, пусто: {}", 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!("сняли {:?} и {:?}, осталось: {:?}", first, last, deque);
}

Вывод:

[1, 2, 3]
спереди: Some(1), сзади: Some(3)
длина: 3, пусто: false
deque[1] = 2
get(9) = None
сняли Some(1) и Some(3), осталось: [2]

▶ Попробуй сам

front и back позволяют посмотреть на элемент, не удаляя его. Индекс deque[1] работает так же, как у Vec, и паникует, если индекс слишком большой, так что, когда не уверен, используй get.

VecDeque можно собрать из Vec, перебрать в цикле и снова превратить в Vec или срез, когда это нужно другой функции:

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);
    }

    // Нужен обычный срез? make_contiguous выстраивает всё в памяти подряд.
    let songs = playlist.make_contiguous();
    songs.sort();
    println!("по алфавиту: {:?}", songs);

    // Или превращаем всё обратно в Vec.
    let as_vec: Vec<&str> = playlist.into();
    println!("как Vec: {:?}", as_vec);
}

Вывод:

1. Count-in
2. Intro
3. Verse
4. Chorus
5. Outro
по алфавиту: ["Chorus", "Count-in", "Intro", "Outro", "Verse"]
как Vec: ["Chorus", "Count-in", "Intro", "Outro", "Verse"]

▶ Попробуй сам

Названия частей песни оставлены на английском, потому что результат зависит от сортировки по буквам. Зачем нужен make_contiguous? Вспомни круглый стол: после нескольких обходов по кругу элементы могут оказаться в двух отдельных кусках памяти. make_contiguous собирает их в один кусок и отдаёт обычный срез, так что можно пользоваться инструментами срезов вроде sort. Нужен он нечасто, но знать о нём полезно.

Где VecDeque пригодится на деле

Вот три повседневные задачи, для которых VecDeque подходит идеально.

Очередь задач «первым пришёл — первым ушёл». Задания на печать ждут в очереди. Новые встают в конец, принтер берёт спереди. Срочное задание всё равно может пролезть вперёд через push_front:

use std::collections::VecDeque;

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

    // Срочно! Это задание встаёт в начало очереди.
    print_queue.push_front("boarding-pass.pdf");

    while let Some(job) = print_queue.pop_front() {
        println!("Печатаю {job} (в очереди ещё {})", print_queue.len());
    }
    println!("Всё готово. Очередь пуста: {}", print_queue.is_empty());
}

Вывод:

Печатаю boarding-pass.pdf (в очереди ещё 3)
Печатаю report.pdf (в очереди ещё 2)
Печатаю photo.jpg (в очереди ещё 1)
Печатаю invoice.pdf (в очереди ещё 0)
Всё готово. Очередь пуста: true

▶ Попробуй сам

while let Some(job) = ...pop_front() — классический цикл очереди. Он продолжается, пока pop_front не вернёт None, то есть пока очередь не опустеет. (Если такая конструкция тебе внове, загляни в урок if let и while let.)

История «последних N элементов». Поле поиска, которое помнит три последних запроса. Когда история заполнена, самый старый запрос выпадает спереди:

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(); // забываем самый старый запрос
    }
    recent.push_back(search.to_string());
}

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

    for search in ["книга по rust", "vecdeque", "binary heap", "пицца рядом"] {
        remember(&mut recent, search);
        println!("{:?}", recent);
    }

    // Показываем сначала новые, как это делает поле поиска.
    let newest_first: Vec<&String> = recent.iter().rev().collect();
    println!("сначала новые: {:?}", newest_first);
}

Вывод:

["книга по rust"]
["книга по rust", "vecdeque"]
["книга по rust", "vecdeque", "binary heap"]
["vecdeque", "binary heap", "пицца рядом"]
сначала новые: ["пицца рядом", "binary heap", "vecdeque"]

▶ Попробуй сам

Скользящее среднее. Термометр присылает показание каждую минуту, а тебе нужно среднее за последние три. Каждое новое показание встаёт в конец, а самое старое уходит спереди. Если хранить текущую сумму sum, всё окно заново складывать не придётся:

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(); // самое старое показание уходит
        }

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

Вывод:

[20.0, 22.0, 24.0] -> среднее 22.0
[22.0, 24.0, 23.0] -> среднее 23.0
[24.0, 23.0, 19.0] -> среднее 22.0
[23.0, 19.0, 21.0] -> среднее 21.0

▶ Попробуй сам

unwrap() здесь безопасен: мы снимаем элемент, только когда в окне больше трёх элементов, так что оно не может быть пустым.

BinaryHeap: следующим всегда самый большой

Теперь приёмный покой. Иногда неважно, кто пришёл первым. Нужно «дай мне самое важное», снова и снова, пока приходят новые дела.

Можно складывать всё в Vec и каждый раз сортировать. Но сортировать всё ради одного верхнего элемента — много лишней работы. BinaryHeap (двоичная куча) держит элементы упорядоченными лишь приблизительно — ровно настолько, чтобы самый большой всегда был наверху. Добавить элемент или забрать верхний — дёшево (O(log n), а это растёт очень медленно: около 17 шагов для 100 000 элементов).

BinaryHeap в Rust — это max-куча (max-heap): pop всегда отдаёт самое большое значение. Вот ставки на аукционе:

use std::collections::BinaryHeap;

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

    println!("наибольшая ставка: {:?}", bids.peek());
    println!("всего ставок: {}", bids.len());

    while let Some(bid) = bids.pop() {
        println!("следующая: {bid}");
    }

    let heap = BinaryHeap::from(vec![5, 1, 4, 2, 3]);
    println!("по порядку: {:?}", heap.into_sorted_vec());
}

Вывод:

наибольшая ставка: Some(450)
всего ставок: 4
следующая: 450
следующая: 300
следующая: 120
следующая: 80
по порядку: [1, 2, 3, 4, 5]

▶ Попробуй сам

peek смотрит на верхний элемент, не снимая его. pop снимает его. into_sorted_vec расходует кучу и отдаёт Vec, отсортированный от меньшего к большему. Как и у VecDeque, peek и pop возвращают Option, так что пустая куча никогда не приводит к падению.

Min-куча с помощью Reverse

А если первым нужно самое маленькое? Ближайшая точка доставки, самый дешёвый рейс, самый ранний дедлайн. Другая коллекция не нужна. Оберни каждое значение в std::cmp::Reverse — он просто переворачивает сравнение: что было самым большим, становится самым маленьким.

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

fn main() {
    // Точки доставки по расстоянию в км. Всегда едем к ближайшей.
    let mut stops = BinaryHeap::new();
    for km in [12, 3, 8, 5] {
        stops.push(Reverse(km));
    }

    if let Some(Reverse(closest)) = stops.peek() {
        println!("ближайшая точка: {closest} км");
    }

    while let Some(Reverse(km)) = stops.pop() {
        println!("едем {km} км");
    }
}

Вывод:

ближайшая точка: 3 км
едем 3 км
едем 5 км
едем 8 км
едем 12 км

▶ Попробуй сам

Reverse(km) — это крошечная структура-обёртка. Образец Some(Reverse(km)) разворачивает оба слоя сразу, и ты получаешь обычное число.

Очередь с приоритетом из структур

Настоящие задачи — не просто числа. У них есть название, приоритет, может быть, время поступления. Чтобы положить свою структуру в BinaryHeap, Rust должен знать, как сравнить две такие структуры, то есть структура должна реализовать Ord (см. Популярные трейты).

Быстрее всего — через derive. Одно важное правило: derive сравнивает поля сверху вниз. Сначала сравнивается первое поле, и только если они равны — второе. Так что поле, по которому нужно сортировать, ставь первым:

use std::collections::BinaryHeap;

// Порядок полей важен: derive сравнивает сначала `priority`, потом `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: "book dentist".to_string() });
    todo.push(Task { priority: 5, name: "fix the outage".to_string() });
    todo.push(Task { priority: 1, name: "water plants".to_string() });
    todo.push(Task { priority: 2, name: "reply to email".to_string() });

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

Вывод:

[5] fix the outage
[2] reply to email
[2] book dentist
[1] water plants

▶ Попробуй сам

Названия задач здесь оставлены на английском: при равном приоритете порядок решает сортировка по буквам, и пример показывает именно её. («book dentist» — записаться к стоматологу, «fix the outage» — устранить сбой, «water plants» — полить цветы, «reply to email» — ответить на письмо.) Если поменять поля местами, чтобы name шло первым, куча упорядочит задачи по алфавиту и почти полностью проигнорирует приоритет. Лёгкая ошибка и тихий баг.

Посмотри на две задачи с приоритетом 2. «book dentist» пришла первой, но первой вышла «reply to email». Ничью разрешило поле name, а «reply» побеждает «book», потому что идёт в алфавите позже. Это предсказуемо, но, скорее всего, не то, что тебе нужно. Обычно при равенстве первой должна идти задача, которая пришла раньше. Для такого особого правила напиши Ord сам:

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

#[derive(Debug, PartialEq, Eq)]
struct Job {
    priority: u8,
    id: u32, // порядок поступления: меньший id пришёл раньше
    name: String,
}

impl Ord for Job {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority
            .cmp(&other.priority) // побеждает больший приоритет
            .then_with(|| other.id.cmp(&self.id)) // при равенстве побеждает более ранний 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: "book dentist".to_string() });
    jobs.push(Job { priority: 5, id: 2, name: "fix the outage".to_string() });
    jobs.push(Job { priority: 1, id: 3, name: "water plants".to_string() });
    jobs.push(Job { priority: 2, id: 4, name: "reply to email".to_string() });

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

Вывод:

[5] #2 fix the outage
[2] #1 book dentist
[2] #4 reply to email
[1] #3 water plants

▶ Попробуй сам

Весь фокус — в then_with: если приоритеты равны, id сравниваются наоборот (other.id с self.id). Из-за этого меньший id считается «бо́льшим» и выходит из max-кучи первым. Не страшно, если это уляжется в голове не сразу. Перевернуть сравнение — ровно то, что делает за тебя Reverse, только здесь это написано вручную. Блок PartialOrd — всегда один и тот же шаблонный код: он просто вызывает твой cmp.

Настоящий алгоритм: три лучших результата

Допустим, у тебя огромный список очков в игре, а нужны только три лучших. Можно отсортировать весь список, но есть изящный приём, при котором в памяти всё время лежат всего три элемента.

Используй min-кучу размером 3. Добавляй каждый результат. Когда в куче становится 4 элемента, снимай один. Раз это min-куча, выбрасываешь ты самый маленький. В конце остаются только три лучших.

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(); // min-куча: наверху лежит наименьший результат

    for score in scores {
        top.push(Reverse(score));
        if top.len() > 3 {
            top.pop(); // четыре — это на один больше: выбрасываем наименьший
        }
    }

    let best: Vec<u32> = top
        .into_sorted_vec()
        .into_iter()
        .map(|Reverse(score)| score)
        .collect();
    println!("тройка лучших: {:?}", best);
}

Вывод:

тройка лучших: [99, 95, 91]

▶ Попробуй сам

Приятный бонус: into_sorted_vec сортирует значения Reverse от «меньшего» к «большему», а для настоящих очков это значит — от большего к меньшему. Поэтому лучший результат выходит первым без всякой дополнительной сортировки. Этот приём работает и для списка из миллиона результатов, держа в памяти не больше четырёх.

Что выбрать?

Вот шпаргалка. «Быстро» значит, что время почти не зависит от размера коллекции. «Медленно» — что оно растёт вместе с размером.

Коллекция	Сильная сторона	Добавить	Взять спереди / сверху	Найти любой элемент
`Vec<T>`	Список с доступом по позиции; стек	Быстро в конец	Медленно (`remove(0)` сдвигает всё)	Медленно (просмотр каждого элемента)
`VecDeque<T>`	Очереди: добавлять и удалять с обоих концов	Быстро с обоих концов	Быстро с обоих концов	Медленно (просмотр каждого элемента)
`BinaryHeap<T>`	«Дай следующим самое большое / срочное»	Довольно быстро (O(log n))	Довольно быстро: всегда самое большое	Медленно, и порядка нет
`BTreeSet<T>`	Уникальные значения, всегда отсортированные	Довольно быстро (O(log n))	Довольно быстро: и наименьшее, и наибольшее	Довольно быстро (O(log n))

Если сомневаешься, начни с Vec. Бери VecDeque, когда забираешь элементы спереди. Бери BinaryHeap, когда снова и снова спрашиваешь «что сейчас важнее всего?». Используй BTreeSet, когда нужны отсортированные уникальные значения и ты хочешь искать элементы, а не только брать верхний.

Частые ошибки

Ждать, что .iter() у BinaryHeap даст отсортированный порядок. Куча упорядочена лишь приблизительно. Самый большой элемент — первый, а остальные лежат в перемешанном порядке, который удобен куче, но не тебе:

use std::collections::BinaryHeap;

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

    println!("через iter:    {:?}", heap.iter().collect::<Vec<_>>());
    println!("по порядку:    {:?}", heap.clone().into_sorted_vec());

    let mut heap = heap;
    print!("pop по одному:");
    while let Some(n) = heap.pop() {
        print!(" {n}");
    }
    println!();
}

Вывод:

через iter:    [9, 8, 2, 5, 3, 1]
по порядку:    [1, 2, 3, 5, 8, 9]
pop по одному: 9 8 5 3 2 1

▶ Попробуй сам

То же самое при выводе кучи через {:?}: ты увидишь внутреннюю мешанину. Если элементы нужны по порядку, снимай их по одному через pop или вызови into_sorted_vec.

Положить в BinaryHeap структуру без Ord. Куча должна сравнивать элементы, чтобы знать, какой положить наверх. Если твою структуру сравнить нельзя, Rust остановит тебя:

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)]`

Компилятор сообщает, что для Ticket не реализован трейт Ord. (Строка "login broken" — «не работает вход» — осталась на английском, потому что компилятор цитирует эту строку кода целиком.) Исправление — добавить над структурой #[derive(PartialEq, Eq, PartialOrd, Ord)] (Ord требует и трёх остальных), а urgency сделать первым полем. Или написать Ord вручную, как в примере с Job выше.

Практика

1. По очереди

Трое друзей — Аня, Бен и Кай — по очереди ходят в настольной игре. Положи их в VecDeque и выведи, кто ходит на ходах с 1 по 5. После своего хода игрок уходит в конец очереди. Подсказка: сними игрока через pop_front, выведи его, а потом верни того же игрока через push_back.

Показать решение

use std::collections::VecDeque;

fn main() {
    let mut players = VecDeque::from(vec!["Аня", "Бен", "Кай"]);

    for turn in 1..=5 {
        let player = players.pop_front().unwrap();
        println!("Ход {turn}: {player}");
        players.push_back(player); // обратно в конец очереди
    }
}

Вывод:

Ход 1: Аня
Ход 2: Бен
Ход 3: Кай
Ход 4: Аня
Ход 5: Бен

▶ Попробуй сам

В VecDeque и начало, и конец — быстрые, так что прокрутка очереди почти ничего не стоит, сколько бы ни было игроков.

2. Приёмный покой

Пациенты поступают с тяжестью состояния от 1 до 5. Самый тяжёлый идёт первым. Если у двух пациентов тяжесть одинаковая, первым идёт тот, кто пришёл раньше. Используй BinaryHeap из кортежей и выведи порядок приёма. Пациенты: Мия (тяжесть 2, пришла 1-й), Лео (5, 2-й), Сэм (2, 3-й), Зоя (4, 4-й). Подсказка: кортежи сравниваются поле за полем, как структура с derive. Попробуй (severity, Reverse(arrival), name).

Показать решение

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

fn main() {
    // (тяжесть, Reverse(номер прихода), имя)
    let mut waiting = BinaryHeap::new();
    waiting.push((2, Reverse(1), "Мия"));
    waiting.push((5, Reverse(2), "Лео"));
    waiting.push((2, Reverse(3), "Сэм"));
    waiting.push((4, Reverse(4), "Зоя"));

    while let Some((severity, Reverse(arrival), name)) = waiting.pop() {
        println!("{name} (тяжесть {severity}, по счёту №{arrival})");
    }
}

Вывод:

Лео (тяжесть 5, по счёту №2)
Зоя (тяжесть 4, по счёту №4)
Мия (тяжесть 2, по счёту №1)
Сэм (тяжесть 2, по счёту №3)

▶ Попробуй сам

Тяжесть сравнивается первой, поэтому первым идёт Лео. У Мии и Сэма тяжесть одинаковая, поэтому решает Reverse(arrival), и побеждает тот, кто пришёл раньше (Мия). Номера прихода у всех разные, так что до сравнения имён дело никогда не доходит.

Итоги

Vec — плохая очередь: remove(0) сдвигает все остальные элементы. VecDeque — кольцевой буфер с быстрыми push/pop на обоих концах.
Используй VecDeque для очередей «первым пришёл — первым ушёл», истории «последних N элементов» и скользящих окон.
BinaryHeap — max-куча: pop и peek всегда дают самый большой элемент, не сортируя всё.
Оберни значения в std::cmp::Reverse, чтобы получить min-кучу (сначала самое маленькое).
Структурам в куче нужен Ord. С derive поля сравниваются сверху вниз, так что ставь приоритет первым. Для особых правил при равенстве пиши Ord вручную.
.iter() у кучи не отсортирован. Снимай элементы по одному или используй into_sorted_vec.

Проверь себя

1. Почему на длинном списке VecDeque::pop_front быстрее, чем Vec::remove(0)?

2. Ты добавил в BinaryHeap числа 4, 9 и 2. Что вернёт первый pop()?

3. Как заставить BinaryHeap отдавать первым самое маленькое значение?

4. Структура получает Ord через derive, поля идут так: name, потом priority. Что определяет порядок в BinaryHeap?

Результат: 0 / 4

Что почитать

std::collections — документация стандартной библиотеки (на английском): официальное руководство «какую коллекцию когда использовать» с таблицей скорости для каждой коллекции.
VecDeque — документация стандартной библиотеки (на английском): все методы, включая rotate_left, range, retain и as_slices.
BinaryHeap — документация стандартной библиотеки (на английском): все методы кучи, а также примеры min-кучи с Reverse и peek_mut.
Reverse — документация стандартной библиотеки (на английском): крошечная обёртка, которая переворачивает любое сравнение, с примерами сортировки в обратном порядке.
Общие коллекции — книга «Язык программирования Rust»: глава о векторах, строках и хеш-таблицах — коллекциях, которыми ты будешь пользоваться вместе с этими (перевод на русский).