I want to create a personal web crawler. As I download each page, I collect a new list of URLs. To increase the likelihood that I am downloading the most important pages first, I want to keep the list of URLs to visit sorted by length (shorter URLs are more likely to be closer to the front page). That presents a problem though, because I'm also adding URLs.
A naïve list (Vec<T> in Rust), won't be very efficient. After every batch of inserts, I would need to re-sort the list. Wouldn't it be good if there were a data structure that could maintain the sort order itself? Yes! It's called a binary heap.
Data structures! If you want to keep a list of things in sorted order, even while inserting and deleting items, use a binary heap en.m.wikipedia.org/wiki/Binary_he…08:03 AM - 28 Oct 2022
Rust's standard library provides a binary heap implementation, as std::collections::BinaryHeap. In my case, I want to sort a list of url::Url. By default, they are sorted in alphabetic order.
use url::Url;
use std::collections::BinaryHeap;
fn main() {
let raw_urls = vec![
"https://www.youtube.com/watch?v=ywskA8CoulM",
"https://tim.mcnamara.nz/",
"https://github.com/rust-lang/rust/issues?labels=E-easy&state=open",
];
let mut urls = BinaryHeap::new();
for url in raw_urls {
urls.push(Url::parse(url).unwrap());
}
while let Some(url) = urls.pop() {
println!("{:?}", url.as_str());
}
}
This prints our URLs, but in alphabetic order:
"https://www.youtube.com/watch?v=ywskA8CoulM"
"https://tim.mcnamara.nz/"
"https://github.com/rust-lang/rust/issues?labels=E-easy&state=open"
Unfortunately, it's a little bit complicated to ask BinaryHeap to use a custom sort order. To change the default, I create a new type that wraps one as ShortestFirst(Url). Then, I implement Ord and PartialOrd traits.
use url::Url;
use std::collections::BinaryHeap;
#[derive(PartialEq, Eq, , Debug)]
struct ShortestFirst(Url);
impl PartialOrd for ShortestFirst {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl Ord for ShortestFirst {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
let left = (other.0).as_str().len();
let right = (self.0).as_str().len();
left.cmp(&right)
}
}
fn main() {
let raw_urls = vec![
"https://www.youtube.com/watch?v=ywskA8CoulM",
"https://tim.mcnamara.nz/",
"https://github.com/rust-lang/rust/issues?labels=E-easy&state=open",
];
let mut urls = BinaryHeap::new();
for url in raw_urls {
urls.push(ShortestFirst(Url::parse(url).unwrap()));
}
while let Some(ShortestFirst(url)) = urls.pop() {
println!("{:?}", url.as_str());
}
}
This prints the URLs, in the order we wanted:
"https://tim.mcnamara.nz/"
"https://www.youtube.com/watch?v=ywskA8CoulM"
"https://github.com/rust-lang/rust/issues?labels=E-easy&state=open"
Top comments (0)