Rust VecDeque 与 BinaryHeap

想想咖啡店门口排的队：新来的人排到队尾，店员先招呼排在最前面的人。再想想医院的候诊室：不管谁先到，病情最急的病人先看。两者都是“排队”，规则却不一样。

Rust 为这两种排队各准备了一种集合。VecDeque 是一条很快的队伍，两端都能加人、也都能走人。BinaryHeap 是优先队列（priority queue）：每次交给你的，总是最大（或者说最紧急）的那个元素。你已经学过 vector，在 HashSet 那一页也简单见过 VecDeque。这一页会讲得更深入，再加上 BinaryHeap。

为什么 Vec 不适合当队列

Vec 其实可以当队列用：用 push 往后加，用 remove(0) 从前面取。能跑，问题出在幕后。

Vec 把元素从位置 0 开始紧挨着存放。删掉第一个元素后，后面所有元素都得往左挪一格，把空位补上。只有 3 个元素时，没人察觉得到。可要是有 100,000 个元素，每次 remove(0) 都要挪动 99,999 个值。这就是“O(n)”的意思：工作量随列表长度一起增长。

VecDeque（读作“vec deck”，是 double-ended queue 的缩写，意思是双端队列）用环形缓冲区（ring buffer）解决了这个问题。想象一张圆桌，座位都编了号，桌上还立着一块小牌子：“队伍从这里开始”。第一个人离开时，谁都不用起身，只要把牌子挪到下一个座位就行。新来的人发现最后一个座位已经有人，就坐到 0 号座位（如果空着的话），绕着桌子转了一圈。在任何一端添加或删除，都只是“挪一下牌子”或者“坐满一个座位”，所以不管队伍多长，花的时间都一样少。这就是“O(1)”。

use std::collections::VecDeque;

fn main() {
    // 把 Vec 当队列用：能用，但 remove(0) 会让所有人往左挪
    let mut vec_line = vec!["Ana", "Ben", "Cai"];
    let served = vec_line.remove(0);
    println!("Vec 接待了 {served}，还在等：{:?}", vec_line);

    // VecDeque：pop_front 只是挪动它的“起点”标记
    let mut deque_line = VecDeque::from(vec!["Ana", "Ben", "Cai"]);
    let served = deque_line.pop_front();
    println!("VecDeque 接待了 {:?}，还在等：{:?}", served, deque_line);
}

输出：

Vec 接待了 Ana，还在等：["Ben", "Cai"]
VecDeque 接待了 Some("Ana")，还在等：["Ben", "Cai"]

▶ 动手试一试

结果看起来一样，区别在速度，而且只有队伍变长时才会显现出来。还有一点值得注意：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 用法一样，索引太大时会 panic，所以拿不准的时候就用 get。

你还可以从 Vec 创建 VecDeque，用循环遍历它；别的函数需要 Vec 或 slice 时，也能再转回去：

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

    // 需要普通的 slice？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"]

▶ 动手试一试

曲目名保留了英文：sort 按字母顺序排列，用英文更容易看清排序的结果。

为什么需要 make_contiguous？回想一下那张圆桌：绕过一圈以后，元素可能分成内存里不相连的两段。make_contiguous 把它们整理成一段，再交给你一个普通的 slice，这样就能用 sort 这类 slice 工具了。它不常用，但知道有这么个方法总没错。

VecDeque 的实际用途

下面是三个很适合用 VecDeque 的日常场景。

先进先出（FIFO）的任务队列。 打印任务排队等候：新任务排到队尾，打印机从队首取。紧急的任务还可以用 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。）

“最近 N 条”历史记录。 一个搜索框，只记住你最近 3 次搜索。记满以后，最旧的一条从队首掉出去：

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"]

▶ 动手试一试

滑动窗口平均值。 温度计每分钟发来一个读数，你想知道最近 3 个读数的平均值。每个新读数从队尾加入，最旧的从队首离开。随时维护一个总和 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() 是安全的：只有窗口里超过 3 个元素时才会取出，所以它不可能是空的。

BinaryHeap：下一个总是最大的

现在轮到医院候诊室了。有时候你并不在乎谁先来，你想要的是“把最重要的给我”，一遍又一遍，同时新的东西还在源源不断地进来。

你可以把所有东西放进 Vec，每次都排序一遍。可为了找出最上面的一个就把全部排序，白白浪费了很多工夫。BinaryHeap 只把元素大致整理一下，刚好保证最大的那个永远在最上面。添加一个元素或取走最上面的元素都很便宜（O(log n)，增长得非常慢：100,000 个元素也只要大约 17 步）。

Rust 的 BinaryHeap 是最大堆（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，所以堆空了也不会崩溃。

用 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} km");
    }

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

输出：

最近的送货点：3 km
开 3 km
开 5 km
开 8 km
开 12 km

▶ 动手试一试

Reverse(km) 是一个很小的包装结构体。Some(Reverse(km)) 这个模式一次剥掉两层，你拿到的就是普通的数字。

结构体的优先队列

真实的任务可不只是数字。它们有名字、有优先级，可能还有到达时间。要把你自己的结构体放进 BinaryHeap，Rust 得知道怎样比较两个结构体，也就是说，这个结构体必须实现 Ord（见常用 trait）。

最快的办法是 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

▶ 动手试一试

任务名（“预约牙医”“修复故障”“给植物浇水”“回复邮件”）保留了英文：优先级相同时，顺序由名字的字母顺序决定，用英文更容易看出这一点。

如果你把两个字段调换一下，让 name 排在前面，堆就会按字母顺序排列任务，几乎完全无视优先级。这种错误很容易犯，而且是悄无声息的 bug。

看看那两个优先级为 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 反而算“更大”，于是先从最大堆里出来。一时没想明白也没关系。把比较反过来，正是 Reverse 替你做的事，这里只是手写了一遍。PartialOrd 那一段永远是同样的样板代码：直接调用你的 cmp。

实战算法：找出前 3 名

假设你有一大串游戏分数，只想要前 3 名。把整个列表排序当然可以，但还有个巧妙的办法，自始至终只留 3 个元素。

用一个大小为 3 的最小堆：每个分数都放进去，堆里一有 4 个元素就取出一个。因为是最小堆，扔掉的总是最小的那个。到最后，剩下的就是最好的 3 个。

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(); // 最小堆：最小的分数在最上面

    for score in scores {
        top.push(Reverse(score));
        if top.len() > 3 {
            top.pop(); // 4 个就多了一个：扔掉最小的
        }
    }

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

输出：

前 3 名：[99, 95, 91]

▶ 动手试一试

还有个意外收获：into_sorted_vec 把 Reverse 值从“最小”排到“最大”，换成真实分数就是从大到小。所以最高分自然排在第一位，不需要再排一次序。哪怕有一百万个分数，这个方法在内存里也最多只放 4 个。

该用哪一个？

下面是一张速查表。“快”表示不管集合多大，耗时都差不多；“慢”表示耗时随集合大小增长。

集合	擅长	添加	从队首／堆顶取出	查找任意元素
Vec<T>	按位置读取的列表；栈	在末尾很快	慢（remove(0) 要挪动所有元素）	慢（逐个查看）
VecDeque<T>	队列：两端都能添加和删除	两端都快	两端都快	慢（逐个查看）
BinaryHeap<T>	“下一个给我最大／最紧急的”	比较快（O(log n)）	比较快：总是最大的	慢，而且没有排好的顺序
BTreeSet<T>	不重复的值，始终保持有序	比较快（O(log n)）	比较快：最小的和最大的都行	比较快（O(log n)）

拿不准的时候，先用 Vec。需要从前面取东西时，换成 VecDeque。总是在问“现在最重要的是哪个？”时，换成 BinaryHeap。需要有序、不重复的值，而且不只是取最上面那个、还要查找元素时，用 BTreeSet。

常见误区

以为 BinaryHeap 的 .iter() 是排好序的。 堆只是大致有序。最大的元素排在第一，其余的顺序乱糟糟的，对堆有用，对你却没什么用：

use std::collections::BinaryHeap;

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

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

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

输出：

iter:   [9, 8, 2, 5, 3, 1]
sorted: [1, 2, 3, 5, 8, 9]
popped: 9 8 5 3 2 1

▶ 动手试一试

这个例子的标签（iter、sorted＝排序后、popped＝依次取出）保留了英文，因为它们靠空格对齐，中文字符占两个字符宽，会把对齐打乱。

用 {:?} 打印堆也是一样，你看到的是内部那种乱序。如果需要按顺序拿到元素，就一个一个 pop，或者调用 into_sorted_vec。

把没有实现 Ord 的结构体放进 BinaryHeap。 堆必须比较元素，才能知道哪个放在最上面。如果你的结构体没法比较，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 trait”，help 那一行建议你给它加上 #[derive(Ord)]。这是编译器的原文，所以保留英文。

修复方法是在结构体上方加上 #[derive(PartialEq, Eq, PartialOrd, Ord)]（Ord 还需要另外三个），并把 urgency 放在第一个字段。或者像上面的 Job 例子那样，手写 Ord。

练习

1. 轮流上场

Ana、Ben 和 Cai 三个朋友在玩桌游，轮流上场。把他们放进一个 VecDeque，打印第 1 到第 5 轮由谁来玩。每轮结束后，这位玩家回到队尾。提示：先 pop_front 取出玩家并打印，再把同一位玩家 push_back 回去。

查看答案

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!("第 {turn} 轮：{player}");
        players.push_back(player); // 回到队伍末尾
    }
}

输出：

第 1 轮：Ana
第 2 轮：Ben
第 3 轮：Cai
第 4 轮：Ana
第 5 轮：Ben

▶ 动手试一试

在 VecDeque 里，队首和队尾都很快，所以不管有多少玩家，让队伍转起来几乎不花什么代价。

2. 急诊室

病人到达时带着 1 到 5 的严重程度，最严重的先看。严重程度相同的话，先到的先看。用一个元组的 BinaryHeap，打印病人就诊的顺序。病人分别是：Mia（严重程度 2，第 1 个到）、Leo（5，第 2 个到）、Sam（2，第 3 个到）、Zoe（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), "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}（严重程度 {severity}，第 {arrival} 个到）");
    }
}

输出：

Leo（严重程度 5，第 2 个到）
Zoe（严重程度 4，第 4 个到）
Mia（严重程度 2，第 1 个到）
Sam（严重程度 2，第 3 个到）

▶ 动手试一试

严重程度最先比较，所以 Leo 第一个看。Mia 和 Sam 严重程度相同，于是由 Reverse(arrival) 决定，先到的 Mia 胜出。因为每个到达编号都不一样，所以永远用不到名字来打破平局。

总结

• Vec 不适合当队列：remove(0) 要挪动其他所有元素。VecDeque 是一个环形缓冲区，两端的 push／pop 都很快。
• 先进先出的队列、“最近 N 条”历史记录、滑动窗口，都适合用 VecDeque。
• BinaryHeap 是最大堆：pop 和 peek 总是给你最大的元素，不需要把所有东西排序。
• 把值包进 std::cmp::Reverse，就得到最小堆（最小的先出来）。
• 放进堆里的结构体需要实现 Ord。用 derive 时，字段从上到下依次比较，所以要把优先级放在最前面。想自定义平局规则，就手写 Ord。
• 堆的 .iter() 不是有序的。要么一个一个 pop，要么用 into_sorted_vec。

小测验

小测验

1. 在很长的列表上，为什么 VecDeque::pop_front 比 Vec::remove(0) 快？

VecDeque 存的元素更少 Vec::remove(0) 要把其他所有元素往左挪，而 VecDeque 只是移动它的起点位置 VecDeque 会先把元素排好序 两者没有区别

2. 你把 4、9、2 放进一个 BinaryHeap。第一次 pop() 返回什么？

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

3. 怎样让 BinaryHeap 先给你最小的值？

把每个值包进 std::cmp::Reverse 对堆调用 .reverse() 用 pop_front 代替 pop 做不到，只能用 Vec

4. 一个结构体 derive 了 Ord，字段依次是 name 和 priority。在 BinaryHeap 里，顺序由什么决定？

只看 priority Rust 会挑最有用的字段 放入元素的先后顺序 先看 name，priority 只在平局时起作用

得分: 0 / 4

延伸阅读

• std::collections — 标准库文档（英文）：官方的“什么时候该用哪种集合”指南，附有每种集合的速度对照表。
• VecDeque — 标准库文档（英文）：所有方法，包括 rotate_left、range、retain 和 as_slices。
• BinaryHeap — 标准库文档（英文）：堆的所有方法，还有用 Reverse 实现最小堆和使用 peek_mut 的示例。
• Reverse — 标准库文档（英文）：能把任何比较反过来的小包装类型，附有倒序排序的示例。
• 常见集合 —《Rust 程序设计语言》：讲解 vector、字符串和哈希 map 的一章，它们都是你会和本页集合搭配使用的集合。