RustのVecDequeとBinaryHeap

カフェのレジに並ぶ列を思い浮かべてください。新しく来た人は列の後ろに並び、店員さんは先頭の人から順に注文を受けます。今度は病院の待合室を思い浮かべてください。そこでは、いつ来たかに関係なく、いちばん緊急度の高い患者さんが先に診てもらえます。どちらも「待ち行列」ですが、ルールが違います。

Rustには、それぞれにぴったりのコレクションがあります。VecDeque は、両端から追加も削除もできる速い列です。BinaryHeap は優先度付きキュー（priority queue）で、いつもいちばん大きい（いちばん緊急な）要素を次に渡してくれます。ベクタはもう知っていますね。HashSetのページでは VecDeque を少しだけ紹介しました。このページではそれをもっと深く掘り下げ、さらに BinaryHeap も紹介します。

Vecがキューに向かない理由

Vec をキューとして使うことはできます。push で追加し、remove(0) で先頭から取り出せば動きます。問題は、その裏側で起きていることです。

Vec は要素を位置0から詰めて並べています。先頭の要素を取り除くと、残りの要素が全部ひとつずつ左にずれて、空いたすき間を埋めなければなりません。要素が3つなら誰も気づきません。でも要素が10万個あると、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!["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 と同じように使えますが、インデックスが大きすぎるとパニックします。自信がないときは get を使いましょう。

Vec から VecDeque を作ったり、ループで回したり、ほかの関数が必要としているときに 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"]

▶ 実際に試してみよう

曲名は英語のままにしています。sort はアルファベット順に並べるので、そのほうが結果を追いやすいからです。

なぜ make_contiguous が必要なのでしょうか。丸いテーブルを思い出してください。ぐるっと一周したあとだと、要素がメモリ上で2つの別々のかたまりに分かれていることがあります。make_contiguous はそれをひとつのかたまりにまとめ、ふつうのスライスとして渡してくれます。だから sort のようなスライス用の道具が使えるのです。使う機会は多くありませんが、あることを知っておくと役に立ちます。

VecDequeの実際の使い道

VecDeque がぴったりはまる、身近な仕事を3つ紹介します。

先入れ先出し（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"]

▶ 実際に試してみよう

移動平均（スライディングウィンドウ）。 温度計が1分ごとに測定値を送ってきて、直近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 に入れて、毎回並べ替えることもできます。でも、いちばん上の1つを見つけるためだけに全部を並べ替えるのは、ずいぶん無駄な作業です。BinaryHeap は要素をゆるくしか整理していません。いちばん大きいものが常に一番上にある、という程度にだけです。要素を追加するのも、一番上を取り出すのも手軽です（O(log n)。これはとてもゆっくりしか増えず、10万個でも約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 で包むだけです。Reverse は比較をひっくり返すので、いちばん大きかったものが、いちばん小さいものとして扱われます。

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

fn main() {
    // 配達先までの距離（km）。いつも次にいちばん近いところへ向かう
    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)) というパターンで2つの層を一度にはがせるので、ふつうの数値が手に入ります。

構造体の優先度付きキュー

現実のタスクは、ただの数値ではありません。名前があり、優先度があり、到着した時刻もあるかもしれません。自分の構造体を BinaryHeap に入れるには、2つの値をどう比べるかをRustが知っている必要があります。つまり、構造体が Ord を実装していなければなりません（よく使うトレイトを参照）。

いちばん手軽なのは derive です。ひとつ知っておいてほしいのは、deriveはフィールドを上から順に比べるということです。まず最初のフィールドを比べ、それが等しいときだけ2番目のフィールドを見ます。ですから、並べ替えの基準にしたいフィールドを最初に書きましょう。

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

▶ 実際に試してみよう

タスク名（「メールに返信」「障害を直す」「植物に水をやる」「歯医者を予約」）は英語のままにしています。優先度が同じときは名前のアルファベット順で順番が決まるので、その様子がわかりやすいからです。

もし2つのフィールドを入れ替えて name を先にすると、ヒープはタスクをアルファベット順に並べ、優先度はほとんど無視されてしまいます。うっかりやりがちで、しかも気づきにくいバグです。

優先度2のタスク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を逆向きに比べます（self.id と other.id ではなく、other.id と self.id）。こうすると小さいidのほうが「大きい」とみなされ、最大ヒープから先に出てきます。すぐに飲み込めなくても大丈夫です。比較をひっくり返すのは Reverse がやってくれることそのもので、それを手で書いただけです。PartialOrd のブロックはいつも同じ決まり文句で、自分の cmp を呼ぶだけです。

実践アルゴリズム：上位3つのスコア

ゲームのスコアが大量にあって、上位3つだけが欲しいとします。リスト全体を並べ替えてもできますが、要素を常に3つしか持たない、うまい方法があります。

サイズ3の最小ヒープを使います。スコアをひとつずつ入れていき、ヒープの要素が4つになったら1つ取り出します。最小ヒープなので、捨てられるのはいちばん小さいスコアです。最後には、上位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つは1つ多すぎる: いちばん小さいものを捨てる
        }
    }

    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 の値を「小さい順」に並べますが、これは本当のスコアでいうと大きい順です。ですから、余分な並べ替えをしなくても、いちばん良いスコアが先頭に来ます。このやり方なら、スコアが100万個あっても、メモリに置くのは常に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 トレイトが実装されていない」というエラーで、help の行では #[derive(Ord)] を付けるよう提案しています。コンパイラのメッセージなので英語のままです。

直し方は、構造体の上に #[derive(PartialEq, Eq, PartialOrd, Ord)] を付けることです（Ord にはほかの3つも必要です）。そして urgency を最初のフィールドにします。または、上の Job の例のように Ord を手で書きましょう。

練習問題

1. 順番に交代する

Ana、Ben、Cai の3人の友だちが、ボードゲームで順番に遊びます。3人を 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 が速いです。
• VecDeque は、先入れ先出しのキュー、「直近N件」の履歴、スライディングウィンドウに使いましょう。
• 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. BinaryHeap に 4、9、2 を入れました。最初の pop() は何を返しますか？

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

3. BinaryHeap からいちばん小さい値を先に取り出すにはどうしますか？

それぞれの値を std::cmp::Reverse で包む ヒープに対して .reverse() を呼ぶ pop の代わりに pop_front を使う できないので Vec を使う

4. ある構造体が、フィールド name、priority の順で Ord をderiveしています。BinaryHeap での順番を決めるのは何ですか？

priority だけ Rustがいちばん役に立つフィールドを選ぶ 要素を入れた順番 まず name。priority は同点のときだけ使われる

スコア: 0 / 4

さらに詳しく

• std::collections — 標準ライブラリのドキュメント（英語）：公式の「どのコレクションをいつ使うべきか」ガイドです。すべてのコレクションの速さを比べた表もあります。
• VecDeque — 標準ライブラリのドキュメント（英語）：rotate_left、range、retain、as_slices を含む、すべてのメソッドが載っています。
• BinaryHeap — 標準ライブラリのドキュメント（英語）：ヒープのすべてのメソッドに加え、Reverse を使った最小ヒープや peek_mut の例があります。
• Reverse — 標準ライブラリのドキュメント（英語）：どんな比較でもひっくり返す小さなラッパーです。逆順に並べ替える例もあります。
• 一般的なコレクション — The Rust Programming Language 日本語版：ベクタ、文字列、ハッシュマップについての章です。このページのコレクションと一緒に使うことになるものばかりです。