Cấu trúc dữ liệu BinaryHeap trong Rust về cơ bản là một hình thức của hàng đợi ưu tiên chứa các phần tử được lưu trong một cấu trúc Heap. Nó đảm bảo tốc độ truy cập phần tử có giá trị “lớn nhất” sẽ luôn là O(1). Hoặc nếu chúng ta nhìn một cách trực quan hơn thì nó giống như một hàng đợi thông minh luôn đặt đối tượng quan trọng nhất ở vị trí đầu tiên để lấy ra nhanh nhất và như vậy nó rất phù hợp với những bài toán mà chúng ta liên tục phải lấy ra đối tượng có mức ưu tiên cao nhất.
Không giống như các véc-tơ hay hàng đợi thông thường luôn phải sử dụng các thao tác sắp xếp thứ tự, BinaryHeap luôn tự động duy trì thứ tự một phần (”partial order”). Chính vì vậy BinaryHeap rất phù hợp để triển khai các thuật toán kiểu Dijkstra (tìm đường ngắn nhất, xử lý tác vụ ưu tiên hay chỉ đơn thuần khi chúng ta cần thực hiện một thao tác “hãy đưa tôi nhiệm vụ quan trọng nhất kế tiếp”)
use std::collections::BinaryHeap;
fn main() { // Tạo một cấu trúc max-heap // (phần tử lớn nhất luôn ở vị trí đầu tiên) let mut max_heap = BinaryHeap::new(); // Thêm các phần tử vào max-heap // Tự động duy trì trật tự lớn nhất luôn ở đầu max_heap.push(3); max_heap.push(7); max_heap.push(1); max_heap.push(9); // Luôn đảm bảo O(1) khi lấy ra phần tử lớn nhất while let Some(max) = max_heap.pop() { println!("Số lớn nhất kế tiếp: {:?}", max); }
}
Một điểm quan trọng khi sử dụng Binaryheap đó là nó luôn mặc định là max-heap hay phần tử lớn nhất ở vị trí đầu tiên để lấy ra. Do vậy nếu chúng ta muốn ngược lại, hay nói cách khác là phần tử nhỏ nhất sẽ luôn ở vị trí đầu tiên để lấy ra thì sẽ cần phải sử dụng Reverse như trong ví dụ sau:
use std::collections::BinaryHeap;
use std::cmp::Reverse; fn main() { let mut min_heap = BinaryHeap::new(); min_heap.push(Reverse(3)); min_heap.push(Reverse(7)); min_heap.push(Reverse(1)); min_heap.push(Reverse(9)); while let Some(min) = min_heap.pop() { println!("Số nhỏ nhất kế tiếp là: {:?}", min.0); }
}
Nếu chúng ta cần xử lý các bài toán đồ thị, hay các bài toán liên quan đến “knowledge graph” để phối hợp với các mô hình ngôn ngữ lớn hãy nhớ đến BinaryHeap.
Các bạn có thể xem video phân tích chi tiết hơn về BinaryHeap trong Rust tại "#030 - std::collections::BinaryHeap - Mục đích & Cách dùng” trên kênh Youtube RustDEV Vietnam.