Creating a priority queue with a custom sort order using a binary heap in Rust
Tags: rust, datastructures
Published: 2022-10-28 09:13:00

---
title: Creating a priority queue with a custom sort order using a binary heap in Rust
published: true
description: 
tags: rust, datastructures
# cover_image: https://direct_url_to_image.jpg
# Use a ratio of 100:42 for best results.
published_at: 2022-10-28 22:13 +1300
---

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_.

{% embed https://twitter.com/timClicks/status/1585905108029960193 %}

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.


```rust
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. 

```rust
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"
```