VecDeque và BinaryHeap trong Rust

Hãy nghĩ đến hàng người chờ ở quán cà phê. Người mới đến xếp vào cuối hàng, và nhân viên pha chế phục vụ người đứng đầu hàng. Giờ hãy nghĩ đến phòng chờ ở bệnh viện. Ở đó, bệnh nhân nguy kịch nhất được khám trước, bất kể đến lúc nào. Cả hai đều là “hàng chờ”, nhưng theo những luật khác nhau.

Rust có một collection cho mỗi loại. VecDeque là một hàng chờ nhanh, nơi bạn thêm và lấy ra được ở cả hai đầu. BinaryHeap là một hàng đợi ưu tiên (priority queue): nó luôn đưa cho bạn phần tử lớn nhất (hay khẩn cấp nhất) tiếp theo. Bạn đã biết Vector, và bài HashSet đã cho bạn cái nhìn đầu tiên về VecDeque. Bài này đi sâu hơn, và thêm BinaryHeap vào.

Vì sao Vec là một hàng đợi tồi

Bạn có thể dùng Vec làm hàng đợi. Thêm bằng push, lấy ở đầu bằng remove(0). Nó chạy được. Vấn đề nằm ở những gì xảy ra phía sau.

Vec giữ các phần tử xếp sát nhau, bắt đầu từ vị trí 0. Khi bạn xóa phần tử đầu tiên, mọi phần tử còn lại phải trượt sang trái một bước để lấp chỗ trống. Với 3 phần tử, chẳng ai để ý. Với 100.000 phần tử, mỗi lần remove(0) phải di chuyển 99.999 giá trị. Đó là ý nghĩa của “O(n)”: khối lượng công việc tăng theo kích thước danh sách.

VecDeque (đọc là “vec deck”, viết tắt của double-ended queue, hàng đợi hai đầu) giải quyết chuyện này bằng một bộ đệm vòng (ring buffer). Hãy hình dung một cái bàn tròn với các ghế được đánh số, và một tấm biển nhỏ ghi “hàng bắt đầu ở đây”. Khi người đầu tiên rời đi, không ai phải đứng dậy. Bạn chỉ dời tấm biển sang ghế kế tiếp. Khi có người mới đến mà ghế cuối đã có người, họ ngồi vào ghế 0 nếu ghế đó trống, vòng quanh bàn. Thêm hay bớt ở đầu nào cũng chỉ là “dời tấm biển” hoặc “lấp một ghế”, nên nó tốn cùng một chút thời gian bất kể hàng dài bao nhiêu. Đó là “O(1)”.

use std::collections::VecDeque;

fn main() {
    // Vec dùng làm hàng đợi: chạy được, nhưng remove(0) dịch mọi người sang trái.
    let mut vec_line = vec!["Ana", "Ben", "Cai"];
    let served = vec_line.remove(0);
    println!("Vec đã phục vụ {served}, còn chờ: {:?}", vec_line);

    // VecDeque: pop_front chỉ dời dấu "điểm bắt đầu" của nó.
    let mut deque_line = VecDeque::from(vec!["Ana", "Ben", "Cai"]);
    let served = deque_line.pop_front();
    println!("VecDeque đã phục vụ {:?}, còn chờ: {:?}", served, deque_line);
}

Kết quả:

Vec đã phục vụ Ana, còn chờ: ["Ben", "Cai"]
VecDeque đã phục vụ Some("Ana"), còn chờ: ["Ben", "Cai"]

▶ Tự chạy thử

Kết quả trông giống nhau. Khác biệt nằm ở tốc độ, và nó chỉ lộ ra khi hàng dài. Để ý thêm một điều: pop_front trả về một Option. Nếu hàng trống, bạn nhận None thay vì chương trình bị crash.

Cơ bản về VecDeque

VecDeque nằm trong std::collections, nên bạn cần một dòng use. Sau đó, tên các phương thức đọc gần như tiếng Anh thông thường: push hoặc pop, ở front (đầu) hoặc back (cuối).

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!("đầu: {:?}, cuối: {:?}", deque.front(), deque.back());
    println!("độ dài: {}, rỗng: {}", 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!("đã lấy ra {:?} và {:?}, còn lại: {:?}", first, last, deque);
}

Kết quả:

[1, 2, 3]
đầu: Some(1), cuối: Some(3)
độ dài: 3, rỗng: false
deque[1] = 2
get(9) = None
đã lấy ra Some(1) và Some(3), còn lại: [2]

▶ Tự chạy thử

front và back cho phép bạn nhìn mà không lấy ra. Truy cập bằng chỉ số deque[1] hoạt động y như Vec, và panic nếu chỉ số quá lớn, nên hãy dùng get khi bạn không chắc.

Bạn cũng có thể tạo VecDeque từ một Vec, duyệt qua nó, và chuyển nó trở lại thành Vec hay slice khi một hàm khác cần:

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

    // Cần một slice bình thường? make_contiguous xếp mọi thứ liền nhau trong bộ nhớ.
    let songs = playlist.make_contiguous();
    songs.sort();
    println!("đã sắp xếp: {:?}", songs);

    // Hoặc chuyển cả cái về lại thành Vec.
    let as_vec: Vec<&str> = playlist.into();
    println!("dạng Vec: {:?}", as_vec);
}

Kết quả:

1. Count-in
2. Intro
3. Verse
4. Chorus
5. Outro
đã sắp xếp: ["Chorus", "Count-in", "Intro", "Outro", "Verse"]
dạng Vec: ["Chorus", "Count-in", "Intro", "Outro", "Verse"]

▶ Tự chạy thử

Tên các đoạn nhạc được giữ tiếng Anh vì ví dụ sắp xếp chúng theo bảng chữ cái, mà sort so sánh theo byte nên chữ tiếng Việt có dấu sẽ ra thứ tự khác. Vì sao cần make_contiguous? Nhớ lại cái bàn tròn: sau vài lần vòng quanh, các phần tử có thể nằm ở hai mảnh bộ nhớ tách rời. make_contiguous gom chúng lại thành một mảnh và trả cho bạn một slice bình thường, để bạn dùng được các công cụ của slice như sort. Bạn sẽ không cần nó thường xuyên, nhưng biết là nó có thì tốt.

Những ứng dụng thực tế của VecDeque

Đây là ba việc hằng ngày mà VecDeque rất hợp.

Hàng đợi công việc vào trước, ra trước. Các lệnh in xếp hàng chờ. Lệnh mới vào cuối hàng, máy in lấy từ đầu hàng. Một lệnh gấp vẫn có thể chen lên trước bằng 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");

    // Gấp! Lệnh này nhảy lên đầu hàng.
    print_queue.push_front("boarding-pass.pdf");

    while let Some(job) = print_queue.pop_front() {
        println!("Đang in {job} (còn {} lệnh chờ)", print_queue.len());
    }
    println!("Xong hết. Hàng đợi rỗng: {}", print_queue.is_empty());
}

Kết quả:

Đang in boarding-pass.pdf (còn 3 lệnh chờ)
Đang in report.pdf (còn 2 lệnh chờ)
Đang in photo.jpg (còn 1 lệnh chờ)
Đang in invoice.pdf (còn 0 lệnh chờ)
Xong hết. Hàng đợi rỗng: true

▶ Tự chạy thử

while let Some(job) = ...pop_front() là vòng lặp hàng đợi kinh điển. Nó chạy tiếp cho đến khi pop_front trả về None, nghĩa là hàng đã trống. (Xem bài if let nếu dạng này còn mới với bạn.)

Lịch sử “N mục gần nhất”. Một ô tìm kiếm nhớ 3 lần tìm gần nhất của bạn. Khi đã đầy, mục cũ nhất rơi ra khỏi đầu hàng:

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(); // quên lần tìm cũ nhất
    }
    recent.push_back(search.to_string());
}

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

    for search in ["sách rust", "vecdeque", "binary heap", "quán phở gần đây"] {
        remember(&mut recent, search);
        println!("{:?}", recent);
    }

    // Hiện mục mới nhất trước, như một ô tìm kiếm vẫn làm.
    let newest_first: Vec<&String> = recent.iter().rev().collect();
    println!("mới nhất trước: {:?}", newest_first);
}

Kết quả:

["sách rust"]
["sách rust", "vecdeque"]
["sách rust", "vecdeque", "binary heap"]
["vecdeque", "binary heap", "quán phở gần đây"]
mới nhất trước: ["quán phở gần đây", "binary heap", "vecdeque"]

▶ Tự chạy thử

Trung bình cửa sổ trượt. Một nhiệt kế gửi một số đo mỗi phút, và bạn muốn biết trung bình của 3 số đo gần nhất. Mỗi số đo mới vào cuối hàng, còn số đo cũ nhất rời khỏi đầu hàng. Giữ một biến sum cộng dồn nghĩa là bạn không bao giờ phải cộng lại cả cửa sổ:

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(); // số đo cũ nhất rời đi
        }

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

Kết quả:

[20.0, 22.0, 24.0] -> trung bình 22.0
[22.0, 24.0, 23.0] -> trung bình 23.0
[24.0, 23.0, 19.0] -> trung bình 22.0
[23.0, 19.0, 21.0] -> trung bình 21.0

▶ Tự chạy thử

unwrap() ở đây là an toàn: ta chỉ pop khi cửa sổ có hơn 3 phần tử, nên nó không thể rỗng.

BinaryHeap: luôn là phần tử lớn nhất tiếp theo

Giờ đến phòng chờ bệnh viện. Đôi khi bạn không quan tâm ai đến trước. Bạn muốn “đưa tôi thứ quan trọng nhất tiếp theo”, hết lần này đến lần khác, trong khi những thứ mới vẫn liên tục đến.

Bạn có thể đẩy mọi thứ vào một Vec rồi sắp xếp nó mỗi lần. Nhưng sắp xếp toàn bộ chỉ để tìm phần tử đứng đầu là rất phí công. BinaryHeap chỉ giữ các phần tử được sắp xếp lỏng lẻo, vừa đủ để phần tử lớn nhất luôn nằm trên cùng. Thêm một phần tử hay lấy phần tử trên cùng đều rẻ (O(log n), tăng rất chậm: khoảng 17 bước cho 100.000 phần tử).

BinaryHeap của Rust là một max-heap: pop luôn đưa bạn giá trị lớn nhất. Đây là các lượt trả giá trong một buổi đấu giá:

use std::collections::BinaryHeap;

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

    println!("giá cao nhất: {:?}", bids.peek());
    println!("số lượt trả giá: {}", bids.len());

    while let Some(bid) = bids.pop() {
        println!("tiếp theo: {bid}");
    }

    let heap = BinaryHeap::from(vec![5, 1, 4, 2, 3]);
    println!("đã sắp xếp: {:?}", heap.into_sorted_vec());
}

Kết quả:

giá cao nhất: Some(450)
số lượt trả giá: 4
tiếp theo: 450
tiếp theo: 300
tiếp theo: 120
tiếp theo: 80
đã sắp xếp: [1, 2, 3, 4, 5]

▶ Tự chạy thử

peek nhìn phần tử trên cùng mà không lấy nó ra. pop thì lấy ra. into_sorted_vec tiêu thụ heap và trả cho bạn một Vec đã sắp xếp từ nhỏ đến lớn. Giống VecDeque, cả peek và pop đều trả về Option, nên heap rỗng không bao giờ gây crash.

Min-heap với Reverse

Nếu bạn muốn phần tử nhỏ nhất trước thì sao? Điểm giao hàng gần nhất, chuyến bay rẻ nhất, hạn chót sớm nhất. Bạn không cần một collection khác. Hãy bọc mỗi giá trị trong std::cmp::Reverse, thứ đơn giản là đảo ngược phép so sánh: cái từng lớn nhất giờ thành nhỏ nhất.

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

fn main() {
    // Các điểm giao hàng, theo khoảng cách km. Luôn chạy tới điểm gần nhất tiếp theo.
    let mut stops = BinaryHeap::new();
    for km in [12, 3, 8, 5] {
        stops.push(Reverse(km));
    }

    if let Some(Reverse(closest)) = stops.peek() {
        println!("điểm gần nhất: {closest} km");
    }

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

Kết quả:

điểm gần nhất: 3 km
chạy 3 km
chạy 5 km
chạy 8 km
chạy 12 km

▶ Tự chạy thử

Reverse(km) là một struct bọc ngoài rất nhỏ. Mẫu Some(Reverse(km)) tháo cả hai lớp trong một lần, nên bạn nhận lại con số trần.

Hàng đợi ưu tiên chứa struct

Công việc thực tế đâu chỉ là những con số. Chúng có tên, có độ ưu tiên, có thể có cả thời điểm đến. Để đặt struct của bạn vào BinaryHeap, Rust cần biết cách so sánh hai struct, nghĩa là struct phải triển khai Ord (xem bài Các trait thông dụng).

Cách nhanh nhất là derive. Có một điều cần biết: derive so sánh các field từ trên xuống dưới. Nó so sánh field đầu tiên, và chỉ xét field thứ hai nếu các field đầu bằng nhau. Vì thế hãy đặt field bạn muốn dùng để sắp xếp lên đầu:

use std::collections::BinaryHeap;

// Thứ tự field quan trọng: derive so sánh `priority` trước, rồi đến `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);
    }
}

Kết quả:

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

▶ Tự chạy thử

Tên công việc được giữ tiếng Anh vì khi hòa nhau, chúng được so sánh theo bảng chữ cái, và ví dụ này dựa vào đúng thứ tự đó (“book dentist” là đặt lịch nha sĩ, “reply to email” là trả lời email). Nếu bạn đổi chỗ hai field để name đứng trước, heap sẽ sắp xếp công việc theo bảng chữ cái và gần như bỏ qua độ ưu tiên. Lỗi dễ mắc, mà lại âm thầm.

Hãy nhìn hai công việc có độ ưu tiên 2. “book dentist” đến trước, nhưng “reply to email” lại ra trước. Trường hợp hòa được phân xử bằng name, và “reply” thắng “book” vì nó đứng sau trong bảng chữ cái. Điều đó đoán trước được, nhưng có lẽ không phải điều bạn muốn. Thông thường, khi hòa nhau, công việc đến trước nên được làm trước. Với kiểu quy tắc tùy chỉnh như vậy, hãy tự viết Ord:

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

#[derive(Debug, PartialEq, Eq)]
struct Job {
    priority: u8,
    id: u32, // thứ tự đến: id nhỏ hơn là đến sớm hơn
    name: String,
}

impl Ord for Job {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority
            .cmp(&other.priority) // độ ưu tiên cao hơn thắng
            .then_with(|| other.id.cmp(&self.id)) // khi hòa, id sớm hơn thắng
    }
}

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

Kết quả:

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

▶ Tự chạy thử

Mấu chốt nằm ở then_with: nếu độ ưu tiên bằng nhau, so sánh các id theo chiều ngược (other.id với self.id). Điều đó khiến id nhỏ hơn được tính là “lớn hơn”, nên nó ra khỏi max-heap trước. Đừng lo nếu cần một lúc để thấm. Đảo ngược phép so sánh chính là việc Reverse làm giúp bạn, chỉ là ở đây ta tự viết ra. Khối PartialOrd lúc nào cũng là cùng một đoạn code mẫu: nó chỉ gọi cmp của bạn.

Một thuật toán thực tế: 3 điểm cao nhất

Giả sử bạn có một danh sách điểm số trò chơi khổng lồ và chỉ muốn 3 điểm cao nhất. Sắp xếp cả danh sách thì được, nhưng có một mẹo hay chỉ luôn giữ 3 phần tử.

Dùng một min-heap kích thước 3. Đẩy từng điểm số vào. Khi heap có 4 phần tử, pop một cái ra. Vì đây là min-heap, cái bị bỏ đi là cái nhỏ nhất. Cuối cùng, chỉ còn lại 3 điểm cao nhất.

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(); // một min-heap: điểm nhỏ nhất nằm trên cùng

    for score in scores {
        top.push(Reverse(score));
        if top.len() > 3 {
            top.pop(); // bốn là thừa một: bỏ điểm nhỏ nhất
        }
    }

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

Kết quả:

top 3: [99, 95, 91]

▶ Tự chạy thử

Một điểm cộng nhỏ: into_sorted_vec sắp xếp các giá trị Reverse từ “nhỏ nhất” đến “lớn nhất”, mà với điểm số thật thì nghĩa là từ lớn nhất đến nhỏ nhất. Vì vậy điểm cao nhất ra đầu tiên, không cần sắp xếp thêm. Mẫu này chạy được với danh sách một triệu điểm số trong khi chỉ giữ tối đa 4 điểm trong bộ nhớ.

Nên dùng loại nào?

Đây là bảng tra nhanh. “Nhanh” nghĩa là thời gian gần như không đổi dù collection lớn đến đâu. “Chậm” nghĩa là thời gian tăng theo kích thước.

Collection	Giỏi nhất ở	Thêm vào	Lấy ở đầu / trên cùng	Tìm một phần tử bất kỳ
Vec<T>	Danh sách đọc theo vị trí; ngăn xếp (stack)	Nhanh ở cuối	Chậm (remove(0) dịch mọi thứ)	Chậm (xem từng phần tử)
VecDeque<T>	Hàng đợi: thêm và bớt ở cả hai đầu	Nhanh ở cả hai đầu	Nhanh ở cả hai đầu	Chậm (xem từng phần tử)
BinaryHeap<T>	“Đưa tôi phần tử lớn nhất / khẩn cấp nhất tiếp theo”	Khá nhanh (O(log n))	Khá nhanh: luôn là phần tử lớn nhất	Chậm, và không có thứ tự sắp xếp
BTreeSet<T>	Giá trị không trùng, luôn được sắp xếp	Khá nhanh (O(log n))	Khá nhanh: cả nhỏ nhất lẫn lớn nhất	Khá nhanh (O(log n))

Khi còn phân vân, hãy bắt đầu với Vec. Dùng VecDeque khi bạn lấy phần tử ra từ đầu. Dùng BinaryHeap khi bạn cứ phải hỏi “giờ cái gì quan trọng nhất?”. Dùng BTreeSet khi bạn cần các giá trị không trùng, đã sắp xếp, và muốn tra cứu phần tử chứ không chỉ lấy phần tử trên cùng.

Lỗi thường gặp

Tưởng rằng .iter() trên BinaryHeap cho ra thứ tự đã sắp xếp. Heap chỉ được sắp xếp lỏng lẻo. Phần tử lớn nhất đứng đầu, nhưng phần còn lại nằm theo một thứ tự lộn xộn có ích cho heap, chứ không có ích cho bạn:

use std::collections::BinaryHeap;

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

    println!("iter:       {:?}", heap.iter().collect::<Vec<_>>());
    println!("sắp xếp:    {:?}", heap.clone().into_sorted_vec());

    let mut heap = heap;
    print!("lần lượt pop:");
    while let Some(n) = heap.pop() {
        print!(" {n}");
    }
    println!();
}

Kết quả:

iter:       [9, 8, 2, 5, 3, 1]
sắp xếp:    [1, 2, 3, 5, 8, 9]
lần lượt pop: 9 8 5 3 2 1

▶ Tự chạy thử

In heap bằng {:?} cũng vậy: bạn sẽ thấy sự lộn xộn bên trong. Nếu cần các phần tử theo thứ tự, hãy pop lần lượt từng cái hoặc gọi into_sorted_vec.

Đưa struct không có Ord vào BinaryHeap. Heap phải so sánh các phần tử để biết cái nào nằm trên cùng. Nếu struct của bạn không so sánh được, Rust sẽ chặn lại:

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

Rustc báo rằng Ticket chưa triển khai trait Ord. Cách sửa là thêm #[derive(PartialEq, Eq, PartialOrd, Ord)] phía trên struct (Ord cần cả ba trait kia), với urgency là field đầu tiên. Hoặc tự viết Ord, giống ví dụ Job ở trên.

Luyện tập

1. Lần lượt chơi

Ba người bạn, Ana, Ben và Cai, lần lượt chơi một trò chơi cờ bàn. Hãy đặt họ vào một VecDeque và in ra ai chơi ở các lượt từ 1 đến 5. Sau mỗi lượt, người chơi quay về cuối hàng. Gợi ý: pop_front người chơi, in ra, rồi push_back lại chính người đó.

Xem lời giải

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!("Lượt {turn}: {player}");
        players.push_back(player); // quay về cuối hàng
    }
}

Kết quả:

Lượt 1: Ana
Lượt 2: Ben
Lượt 3: Cai
Lượt 4: Ana
Lượt 5: Ben

▶ Tự chạy thử

Đầu và cuối của VecDeque đều nhanh, nên xoay vòng hàng gần như không tốn gì, dù có bao nhiêu người chơi.

2. Phòng cấp cứu

Bệnh nhân đến với mức độ nghiêm trọng từ 1 đến 5. Người nặng nhất được khám trước. Nếu hai bệnh nhân có cùng mức độ, ai đến trước được khám trước. Dùng một BinaryHeap chứa tuple và in ra thứ tự bệnh nhân được khám. Bệnh nhân: Mia (mức 2, đến thứ 1), Leo (5, thứ 2), Sam (2, thứ 3), Zoe (4, thứ 4). Gợi ý: tuple được so sánh lần lượt từng phần tử, y như một struct có derive. Hãy thử (severity, Reverse(arrival), name).

Xem lời giải

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} (mức độ {severity}, đến thứ #{arrival})");
    }
}

Kết quả:

Leo (mức độ 5, đến thứ #2)
Zoe (mức độ 4, đến thứ #4)
Mia (mức độ 2, đến thứ #1)
Sam (mức độ 2, đến thứ #3)

▶ Tự chạy thử

Mức độ nghiêm trọng được so sánh trước, nên Leo được khám trước. Mia và Sam hòa nhau về mức độ, nên Reverse(arrival) quyết định, và người đến sớm hơn (Mia) thắng. Vì mỗi số thứ tự đến đều khác nhau, tên không bao giờ cần dùng để phân xử khi hòa.

Tóm tắt

• Vec là một hàng đợi tồi: remove(0) dịch mọi phần tử còn lại. VecDeque là một bộ đệm vòng với push/pop nhanh ở cả hai đầu.
• Dùng VecDeque cho hàng đợi vào trước ra trước, lịch sử “N mục gần nhất”, và cửa sổ trượt.
• BinaryHeap là một max-heap: pop và peek luôn cho phần tử lớn nhất, mà không cần sắp xếp mọi thứ.
• Bọc giá trị trong std::cmp::Reverse để có min-heap (nhỏ nhất trước).
• Struct trong heap cần Ord. Với derive, các field được so sánh từ trên xuống, nên hãy đặt độ ưu tiên lên đầu. Tự viết Ord cho các quy tắc phân xử khi hòa tùy chỉnh.
• .iter() trên heap không cho thứ tự đã sắp xếp. Hãy pop lần lượt từng phần tử, hoặc dùng into_sorted_vec.

Kiểm tra nhanh

Kiểm tra nhanh

1. Vì sao VecDeque::pop_front nhanh hơn Vec::remove(0) trên một danh sách dài?

VecDeque lưu ít phần tử hơn Vec::remove(0) dịch mọi phần tử còn lại sang trái, còn VecDeque chỉ dời vị trí bắt đầu của nó VecDeque sắp xếp phần tử trước Không có khác biệt

2. Bạn đẩy 4, 9 và 2 vào một BinaryHeap. Lần pop() đầu tiên trả về gì?

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

3. Làm sao để BinaryHeap trả về giá trị nhỏ nhất trước?

Bọc mỗi giá trị trong std::cmp::Reverse Gọi .reverse() trên heap Dùng pop_front thay vì pop Không làm được; hãy dùng Vec

4. Một struct derive Ord với các field name rồi đến priority. Điều gì quyết định thứ tự trong BinaryHeap?

Chỉ priority Rust tự chọn field hữu ích nhất Thứ tự bạn đẩy phần tử vào name trước; priority chỉ dùng để phân xử khi hòa

Điểm: 0 / 4

Đọc thêm

• std::collections — tài liệu thư viện chuẩn (tiếng Anh): hướng dẫn chính thức “khi nào nên dùng collection nào?”, với bảng tốc độ cho mọi collection.
• VecDeque — tài liệu thư viện chuẩn (tiếng Anh): mọi phương thức, gồm cả rotate_left, range, retain và as_slices.
• BinaryHeap — tài liệu thư viện chuẩn (tiếng Anh): mọi phương thức của heap, cùng ví dụ về min-heap với Reverse và về peek_mut.
• Reverse — tài liệu thư viện chuẩn (tiếng Anh): lớp bọc nhỏ đảo ngược mọi phép so sánh, kèm ví dụ sắp xếp theo thứ tự ngược.
• Common Collections — The Rust Book (tiếng Anh): chương của Book về vector, chuỗi và hash map, những collection bạn sẽ dùng song song với các collection này.