VecDeque dan BinaryHeap di Rust

Bayangkan antrean di kedai kopi. Orang baru masuk dari belakang, dan barista melayani siapa pun yang ada di depan. Sekarang bayangkan ruang tunggu UGD di rumah sakit. Di sana, pasien yang paling gawat dilayani duluan, tidak peduli kapan dia datang. Keduanya sama-sama “antrean”, tapi aturannya berbeda.

Rust punya koleksi untuk masing-masing. VecDeque adalah antrean cepat yang bisa kamu tambah dan kurangi dari kedua ujungnya. BinaryHeap adalah priority queue (antrean prioritas): ia selalu memberimu item yang paling besar (atau paling mendesak) berikutnya. Kamu sudah kenal vektor, dan halaman HashSet sudah sekilas memperkenalkan VecDeque. Halaman ini membahasnya lebih dalam, lalu menambahkan BinaryHeap.

Kenapa Vec adalah antrean yang buruk

Kamu bisa memakai Vec sebagai antrean. Tambahkan dengan push, ambil dari depan dengan remove(0). Itu berhasil. Masalahnya ada pada apa yang terjadi di balik layar.

Vec menyimpan item-itemnya berdempetan, mulai dari posisi 0. Saat kamu menghapus item pertama, semua item lain harus bergeser satu langkah ke kiri untuk mengisi celahnya. Dengan 3 item, tidak ada yang sadar. Dengan 100.000 item, setiap remove(0) memindahkan 99.999 nilai. Itulah arti “O(n)”: pekerjaannya bertambah seiring ukuran daftarnya.

VecDeque (dibaca “vec deck”, singkatan dari double-ended queue, antrean dua ujung) mengatasi ini dengan ring buffer (buffer melingkar). Bayangkan meja bundar dengan kursi bernomor, dan papan kecil bertuliskan “antrean mulai di sini”. Saat orang pertama pergi, tidak ada yang berdiri. Kamu cukup memindahkan papannya ke kursi berikutnya. Saat ada orang baru datang dan kursi terakhir sudah terisi, dia duduk di kursi 0 kalau kosong, memutari meja. Menambah atau menghapus di ujung mana pun cukup dengan “pindahkan papan” atau “isi satu kursi”, jadi waktunya selalu sama singkatnya, berapa pun panjang antreannya. Itulah “O(1)”.

use std::collections::VecDeque;

fn main() {
    // Vec sebagai antrean: berhasil, tapi remove(0) menggeser semua item ke kiri.
    let mut vec_line = vec!["Ana", "Ben", "Cai"];
    let served = vec_line.remove(0);
    println!("Vec melayani {served}, masih menunggu: {:?}", vec_line);

    // VecDeque: pop_front cukup memindahkan penanda "awal"-nya.
    let mut deque_line = VecDeque::from(vec!["Ana", "Ben", "Cai"]);
    let served = deque_line.pop_front();
    println!("VecDeque melayani {:?}, masih menunggu: {:?}", served, deque_line);
}

Output:

Vec melayani Ana, masih menunggu: ["Ben", "Cai"]
VecDeque melayani Some("Ana"), masih menunggu: ["Ben", "Cai"]

▶ Coba sendiri

Hasilnya terlihat sama. Bedanya ada di kecepatan, dan itu baru terasa saat antreannya panjang. Perhatikan satu hal lagi: pop_front mengembalikan Option. Kalau antreannya kosong, kamu mendapat None, bukan crash.

Dasar-dasar VecDeque

VecDeque berada di std::collections, jadi kamu perlu baris use. Setelah itu, nama method-nya hampir seperti kalimat bahasa Inggris: push (masukkan) atau pop (keluarkan), di front (depan) atau back (belakang).

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!("depan: {:?}, belakang: {:?}", deque.front(), deque.back());
    println!("panjang: {}, kosong: {}", 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!("dikeluarkan {:?} dan {:?}, sisa: {:?}", first, last, deque);
}

Output:

[1, 2, 3]
depan: Some(1), belakang: Some(3)
panjang: 3, kosong: false
deque[1] = 2
get(9) = None
dikeluarkan Some(1) dan Some(3), sisa: [2]

▶ Coba sendiri

front dan back membiarkanmu melihat tanpa mengeluarkan. Akses indeks dengan deque[1] bekerja persis seperti di Vec, dan akan panic kalau indeksnya terlalu besar. Jadi pakai get kalau kamu tidak yakin.

Kamu juga bisa membuat VecDeque dari Vec, melakukan perulangan di atasnya, lalu mengubahnya kembali menjadi Vec atau slice saat fungsi lain membutuhkannya:

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

    // Butuh slice biasa? make_contiguous menyusun semuanya berurutan di memori.
    let songs = playlist.make_contiguous();
    songs.sort();
    println!("terurut: {:?}", songs);

    // Atau ubah semuanya kembali menjadi Vec.
    let as_vec: Vec<&str> = playlist.into();
    println!("sebagai Vec: {:?}", as_vec);
}

Output:

1. Count-in
2. Intro
3. Verse
4. Chorus
5. Outro
terurut: ["Chorus", "Count-in", "Intro", "Outro", "Verse"]
sebagai Vec: ["Chorus", "Count-in", "Intro", "Outro", "Verse"]

▶ Coba sendiri

Nama-nama bagian lagu sengaja dibiarkan dalam bahasa Inggris, karena hasil sort bergantung pada urutan abjadnya.

Kenapa perlu make_contiguous? Ingat meja bundar tadi: setelah beberapa kali memutar, item-itemnya bisa terpisah di dua bagian memori. make_contiguous merapikannya menjadi satu bagian dan memberimu slice biasa, jadi kamu bisa memakai alat untuk slice seperti sort. Kamu tidak akan sering membutuhkannya, tapi bagus untuk tahu bahwa ia ada.

Kegunaan nyata VecDeque

Berikut tiga pekerjaan sehari-hari yang sangat cocok untuk VecDeque.

Antrean tugas first-in, first-out (pertama masuk, pertama keluar). Pekerjaan cetak menunggu dalam antrean. Pekerjaan baru masuk ke belakang, printer mengambil dari depan. Pekerjaan yang mendesak tetap bisa menyerobot ke depan dengan 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");

    // Mendesak! Yang ini langsung lompat ke depan antrean.
    print_queue.push_front("boarding-pass.pdf");

    while let Some(job) = print_queue.pop_front() {
        println!("Mencetak {job} ({} masih menunggu)", print_queue.len());
    }
    println!("Semua selesai. Antrean kosong: {}", print_queue.is_empty());
}

Output:

Mencetak boarding-pass.pdf (3 masih menunggu)
Mencetak report.pdf (2 masih menunggu)
Mencetak photo.jpg (1 masih menunggu)
Mencetak invoice.pdf (0 masih menunggu)
Semua selesai. Antrean kosong: true

▶ Coba sendiri

while let Some(job) = ...pop_front() adalah perulangan antrean yang klasik. Ia terus berjalan sampai pop_front mengembalikan None, yang artinya antreannya sudah kosong. (Lihat if let kalau bentuk ini masih baru untukmu.)

Riwayat “N item terakhir”. Kotak pencarian yang mengingat 3 pencarian terakhirmu. Saat sudah penuh, yang paling lama terlempar keluar dari depan:

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(); // lupakan pencarian yang paling lama
    }
    recent.push_back(search.to_string());
}

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

    for search in ["buku rust", "vecdeque", "binary heap", "pizza terdekat"] {
        remember(&mut recent, search);
        println!("{:?}", recent);
    }

    // Tampilkan yang terbaru dulu, seperti kotak pencarian sungguhan.
    let newest_first: Vec<&String> = recent.iter().rev().collect();
    println!("terbaru dulu: {:?}", newest_first);
}

Output:

["buku rust"]
["buku rust", "vecdeque"]
["buku rust", "vecdeque", "binary heap"]
["vecdeque", "binary heap", "pizza terdekat"]
terbaru dulu: ["pizza terdekat", "binary heap", "vecdeque"]

▶ Coba sendiri

Rata-rata sliding window (jendela geser). Sebuah termometer mengirim satu bacaan setiap menit, dan kamu ingin rata-rata dari 3 bacaan terakhir. Setiap bacaan baru masuk dari belakang, dan yang paling lama keluar dari depan. Dengan menyimpan sum yang terus diperbarui, kamu tidak perlu menjumlahkan seluruh jendela dari awal lagi:

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(); // bacaan paling lama keluar
        }

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

Output:

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

▶ Coba sendiri

unwrap() di sini aman: kita hanya mengeluarkan item saat jendelanya berisi lebih dari 3 item, jadi tidak mungkin kosong.

BinaryHeap: selalu yang terbesar berikutnya

Sekarang ruang tunggu UGD tadi. Kadang kamu tidak peduli siapa yang datang duluan. Yang kamu mau: “berikan aku hal yang paling penting berikutnya”, berulang kali, sementara hal-hal baru terus berdatangan.

Kamu bisa saja memasukkan semuanya ke Vec lalu mengurutkannya setiap kali. Tapi mengurutkan semuanya hanya untuk mencari item teratas itu pekerjaan yang banyak terbuang. BinaryHeap hanya menjaga item-itemnya tersusun secara longgar, cukup supaya item terbesar selalu ada di puncak. Menambah item atau mengambil item teratas itu murah (O(log n), yang tumbuhnya sangat lambat: sekitar 17 langkah untuk 100.000 item).

BinaryHeap di Rust adalah max-heap: pop selalu memberimu nilai yang paling besar. Berikut tawaran-tawaran di sebuah lelang:

use std::collections::BinaryHeap;

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

    println!("tawaran tertinggi: {:?}", bids.peek());
    println!("jumlah tawaran: {}", bids.len());

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

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

Output:

tawaran tertinggi: Some(450)
jumlah tawaran: 4
berikutnya: 450
berikutnya: 300
berikutnya: 120
berikutnya: 80
terurut: [1, 2, 3, 4, 5]

▶ Coba sendiri

peek melihat item teratas tanpa mengeluarkannya. pop mengeluarkannya. into_sorted_vec menghabiskan heap dan memberimu Vec yang terurut dari terkecil ke terbesar. Sama seperti VecDeque, peek dan pop sama-sama mengembalikan Option, jadi heap yang kosong tidak pernah menyebabkan crash.

Min-heap dengan Reverse

Bagaimana kalau kamu ingin yang terkecil duluan? Titik pengantaran terdekat, tiket pesawat termurah, tenggat waktu paling awal. Kamu tidak butuh koleksi lain. Bungkus setiap nilai dengan std::cmp::Reverse, yang cukup membalik perbandingannya: yang tadinya terbesar sekarang jadi terkecil.

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

fn main() {
    // Titik pengantaran, berdasarkan jarak dalam km. Selalu ke yang terdekat dulu.
    let mut stops = BinaryHeap::new();
    for km in [12, 3, 8, 5] {
        stops.push(Reverse(km));
    }

    if let Some(Reverse(closest)) = stops.peek() {
        println!("titik terdekat: {closest} km");
    }

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

Output:

titik terdekat: 3 km
antar ke titik 3 km
antar ke titik 5 km
antar ke titik 8 km
antar ke titik 12 km

▶ Coba sendiri

Reverse(km) adalah struct pembungkus yang sangat kecil. Pattern Some(Reverse(km)) membuka kedua lapisan sekaligus, jadi kamu mendapatkan kembali angka biasanya.

Priority queue berisi struct

Tugas sungguhan bukan sekadar angka. Tugas punya nama, prioritas, mungkin juga waktu kedatangan. Supaya struct buatanmu bisa masuk ke BinaryHeap, Rust perlu tahu cara membandingkan dua struct itu. Artinya struct tersebut harus mengimplementasikan Ord (lihat Trait yang sering dipakai).

Cara tercepat adalah derive. Satu hal yang perlu kamu tahu: derive membandingkan field dari atas ke bawah. Ia membandingkan field pertama, dan baru melihat field kedua kalau field pertamanya sama. Jadi taruh field yang ingin kamu jadikan dasar urutan di posisi pertama:

use std::collections::BinaryHeap;

// Urutan field itu penting: derive membandingkan `priority` dulu, lalu `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: "janji ke dokter gigi".to_string() });
    todo.push(Task { priority: 5, name: "memperbaiki server mati".to_string() });
    todo.push(Task { priority: 1, name: "menyiram tanaman".to_string() });
    todo.push(Task { priority: 2, name: "membalas email".to_string() });

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

Output:

[5] memperbaiki server mati
[2] membalas email
[2] janji ke dokter gigi
[1] menyiram tanaman

▶ Coba sendiri

Kalau kamu menukar kedua field sehingga name ada di atas, heap akan mengurutkan tugas berdasarkan abjad dan hampir sepenuhnya mengabaikan prioritas. Kesalahan ini gampang terjadi, dan bug-nya tidak kelihatan.

Lihat kedua tugas berprioritas 2. Tugas “janji ke dokter gigi” datang lebih dulu, tapi justru “membalas email” yang keluar duluan. Seri itu diputuskan oleh name, dan “membalas” menang atas “janji” karena huruf “m” datang setelah “j” di abjad. Itu bisa ditebak, tapi mungkin bukan yang kamu mau. Biasanya, saat seri, tugas yang datang lebih dulu seharusnya dikerjakan lebih dulu. Untuk aturan khusus seperti itu, tulis Ord sendiri:

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

#[derive(Debug, PartialEq, Eq)]
struct Job {
    priority: u8,
    id: u32, // urutan kedatangan: id yang lebih kecil datang lebih dulu
    name: String,
}

impl Ord for Job {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority
            .cmp(&other.priority) // prioritas lebih tinggi menang
            .then_with(|| other.id.cmp(&self.id)) // kalau seri, id yang lebih awal menang
    }
}

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: "janji ke dokter gigi".to_string() });
    jobs.push(Job { priority: 5, id: 2, name: "memperbaiki server mati".to_string() });
    jobs.push(Job { priority: 1, id: 3, name: "menyiram tanaman".to_string() });
    jobs.push(Job { priority: 2, id: 4, name: "membalas email".to_string() });

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

Output:

[5] #2 memperbaiki server mati
[2] #1 janji ke dokter gigi
[2] #4 membalas email
[1] #3 menyiram tanaman

▶ Coba sendiri

Triknya ada di then_with: kalau prioritasnya sama, bandingkan id-nya secara terbalik (other.id dengan self.id). Dengan begitu id yang lebih kecil dianggap “lebih besar”, sehingga keluar duluan dari max-heap. Tenang saja kalau ini butuh waktu sebentar untuk dicerna. Membalik perbandingan adalah persis yang dilakukan Reverse untukmu, hanya saja kali ini ditulis manual. Blok PartialOrd selalu berupa kode boilerplate yang sama: isinya hanya memanggil cmp milikmu.

Algoritma sungguhan: 3 skor teratas

Misalnya kamu punya daftar skor game yang sangat panjang dan hanya ingin 3 teratas. Mengurutkan seluruh daftar memang berhasil, tapi ada trik keren yang hanya pernah menyimpan 3 item.

Pakai min-heap berukuran 3. Masukkan setiap skor. Saat heap berisi 4 item, keluarkan satu. Karena ini min-heap, yang kamu buang adalah yang terkecil. Di akhir, hanya 3 skor terbaik yang tersisa.

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-heap: skor terkecil ada di puncak

    for score in scores {
        top.push(Reverse(score));
        if top.len() > 3 {
            top.pop(); // empat itu kelebihan satu: buang yang terkecil
        }
    }

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

Output:

3 teratas: [99, 95, 91]

▶ Coba sendiri

Bonus yang menyenangkan: into_sorted_vec mengurutkan nilai Reverse dari “terkecil” ke “terbesar”, yang untuk skor aslinya berarti dari terbesar ke terkecil. Jadi skor terbaik keluar paling depan, tanpa pengurutan tambahan. Pola ini tetap bekerja untuk daftar berisi sejuta skor, sementara memori hanya pernah menyimpan 4 skor.

Mana yang sebaiknya kupakai?

Berikut contekan singkatnya. “Cepat” artinya waktunya kurang lebih tetap sama, sebesar apa pun koleksinya. “Lambat” artinya waktunya bertambah seiring ukurannya.

Koleksi	Unggul untuk	Push	Ambil dari depan / puncak	Mencari item apa saja
Vec<T>	Daftar yang dibaca berdasarkan posisi; stack	Cepat di akhir	Lambat (remove(0) menggeser semuanya)	Lambat (cek satu per satu)
VecDeque<T>	Antrean: tambah dan hapus di kedua ujung	Cepat di kedua ujung	Cepat di kedua ujung	Lambat (cek satu per satu)
BinaryHeap<T>	“Berikan yang terbesar / paling mendesak berikutnya”	Cukup cepat (O(log n))	Cukup cepat: selalu yang terbesar	Lambat, dan tidak terurut
BTreeSet<T>	Nilai unik yang selalu terurut	Cukup cepat (O(log n))	Cukup cepat: terkecil dan terbesar	Cukup cepat (O(log n))

Kalau ragu, mulailah dengan Vec. Beralihlah ke VecDeque saat kamu mengambil item dari depan. Beralihlah ke BinaryHeap saat kamu terus bertanya “apa yang paling penting sekarang?”. Pakai BTreeSet saat kamu butuh nilai unik yang terurut dan ingin mencari item, bukan hanya mengambil yang teratas.

Kesalahan umum

Mengira .iter() pada BinaryHeap itu terurut. Heap hanya tersusun secara longgar. Item terbesar ada di depan, tapi sisanya dalam urutan acak-acakan yang berguna untuk heap, bukan untukmu:

use std::collections::BinaryHeap;

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

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

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

Output:

iter:    [9, 8, 2, 5, 3, 1]
terurut: [1, 2, 3, 5, 8, 9]
di-pop: 9 8 5 3 2 1

▶ Coba sendiri

Hal yang sama berlaku saat mencetak heap dengan {:?}: kamu akan melihat susunan internalnya yang acak-acakan. Kalau kamu butuh item-itemnya secara berurutan, pop satu per satu atau panggil into_sorted_vec.

Memasukkan struct tanpa Ord ke BinaryHeap. Heap harus membandingkan item untuk tahu mana yang ada di puncak. Kalau struct-mu tidak bisa dibandingkan, Rust menghentikanmu:

use std::collections::BinaryHeap;

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

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

Pesan compiler ini artinya: Ticket tidak mengimplementasikan trait Ord, jadi tidak bisa dimasukkan ke BinaryHeap. Solusinya, tambahkan #[derive(PartialEq, Eq, PartialOrd, Ord)] di atas struct (Ord juga butuh tiga trait lainnya), dengan urgency sebagai field pertama. Atau tulis Ord secara manual, seperti contoh Job di atas.

Latihan

1. Bergiliran

Tiga sahabat, Ana, Ben, dan Cai, bermain board game secara bergiliran. Masukkan mereka ke VecDeque dan cetak siapa yang main di giliran 1 sampai 5. Setelah setiap giliran, pemain itu pindah ke belakang antrean. Petunjuk: pop_front pemainnya, cetak, lalu push_back pemain yang sama.

Lihat solusi

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!("Giliran {turn}: {player}");
        players.push_back(player); // kembali ke ujung antrean
    }
}

Output:

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

▶ Coba sendiri

Bagian depan dan belakang VecDeque sama-sama cepat, jadi memutar antrean hampir tidak ada biayanya, berapa pun jumlah pemainnya.

2. Ruang UGD

Pasien datang dengan tingkat keparahan dari 1 sampai 5. Yang paling parah ditangani duluan. Kalau dua pasien punya tingkat keparahan yang sama, yang datang lebih dulu ditangani duluan. Pakai BinaryHeap berisi tuple dan cetak urutan pasien yang ditangani. Pasiennya: Mia (keparahan 2, datang ke-1), Leo (5, ke-2), Sam (2, ke-3), Zoe (4, ke-4). Petunjuk: tuple dibandingkan field demi field, sama seperti struct yang memakai derive. Coba (severity, Reverse(arrival), name).

Lihat solusi

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} (keparahan {severity}, datang ke-{arrival})");
    }
}

Output:

Leo (keparahan 5, datang ke-2)
Zoe (keparahan 4, datang ke-4)
Mia (keparahan 2, datang ke-1)
Sam (keparahan 2, datang ke-3)

▶ Coba sendiri

Tingkat keparahan dibandingkan lebih dulu, jadi Leo ditangani pertama. Mia dan Sam seri dalam keparahan, jadi Reverse(arrival) yang menentukan, dan yang datang lebih awal (Mia) menang. Karena setiap nomor kedatangan berbeda, nama tidak pernah dibutuhkan untuk memutuskan seri.

Ringkasan

• Vec adalah antrean yang buruk: remove(0) menggeser semua item lainnya. VecDeque adalah ring buffer dengan push/pop yang cepat di kedua ujung.
• Pakai VecDeque untuk antrean first-in-first-out, riwayat “N item terakhir”, dan sliding window.
• BinaryHeap adalah max-heap: pop dan peek selalu memberi item terbesar, tanpa mengurutkan semuanya.
• Bungkus nilai dengan std::cmp::Reverse untuk mendapatkan min-heap (terkecil duluan).
• Struct di dalam heap butuh Ord. Dengan derive, field dibandingkan dari atas ke bawah, jadi taruh prioritas di posisi pertama. Tulis Ord sendiri untuk aturan seri yang khusus.
• .iter() pada heap tidak terurut. Keluarkan item satu per satu dengan pop, atau pakai into_sorted_vec.

Kuis singkat

Kuis singkat

1. Kenapa VecDeque::pop_front lebih cepat daripada Vec::remove(0) pada daftar yang panjang?

VecDeque menyimpan lebih sedikit item Vec::remove(0) menggeser semua item lain ke kiri, sedangkan VecDeque cukup memindahkan posisi awalnya VecDeque mengurutkan item-itemnya dulu Tidak ada bedanya

2. Kamu memasukkan 4, 9, dan 2 ke BinaryHeap. Apa yang dikembalikan pop() pertama?

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

3. Bagaimana cara membuat BinaryHeap memberimu nilai terkecil duluan?

Bungkus setiap nilai dengan std::cmp::Reverse Panggil .reverse() pada heap Pakai pop_front, bukan pop Tidak bisa; pakai Vec

4. Sebuah struct memakai derive Ord dengan field name lalu priority. Apa yang menentukan urutannya di BinaryHeap?

Hanya priority Rust memilih field yang paling berguna Urutan saat kamu memasukkan item name dulu; priority hanya untuk memutuskan seri

Skor: 0 / 4

Bacaan lebih lanjut

• std::collections — dokumentasi standard library (bahasa Inggris): panduan resmi “koleksi mana yang sebaiknya dipakai?”, lengkap dengan tabel kecepatan untuk setiap koleksi.
• VecDeque — dokumentasi standard library (bahasa Inggris): semua method-nya, termasuk rotate_left, range, retain, dan as_slices.
• BinaryHeap — dokumentasi standard library (bahasa Inggris): semua method heap, plus contoh min-heap dengan Reverse dan peek_mut.
• Reverse — dokumentasi standard library (bahasa Inggris): pembungkus kecil yang membalik perbandingan apa pun, dengan contoh pengurutan terbalik.
• Common Collections — The Rust Book (bahasa Inggris): bab di Rust Book tentang vektor, string, dan hash map, koleksi yang akan kamu pakai bersama koleksi di halaman ini.