Rust Collections: BinaryHeap and its DSL Operations

In this blog post, we'll explore different Domain Specific Languages (DSL) operations that can be applied on BinaryHeap

BinaryHeap

A priority queue implemented with a binary heap. By default, it will be a max-heap (i.e., when we retrieve values from BinaryHeap using pop(), peek() methods, max value will be returned)

In case, if we use core::cmp::Reverse struct to push items to BinaryHeap, then it will be called as min-heap (i.e., when we retrieve values from BinaryHeap using pop(), peek() methods, min value will be returned)

For more details, please check this page from rust documentation.

BinaryHeap (as max-heap) code examples

Creating new BinaryHeap (max-heap) using new constructor method

    // Create new BinaryHeap (Max-Heap)
    let mut bh = BinaryHeap::new();
    bh.push(10);
    bh.push(20);
    bh.push(30);
    bh.push(40);
    bh.push(50);

Creating new BinaryHeap (max-heap) using From trait's from method

    // Creating BinaryHeap (Max-Heap) using From trait
    let bh1 = BinaryHeap::from([1, 2, 3, 4, 5]);

Creating new BinaryHeap (max-heap) using IntoIterator trait's collect method

    // Creating BinaryHeap (Max-Heap) using IntoInterator trait
    let bh2: BinaryHeap<i32> = vec![1, 2, 3, 4, 5].into_iter().collect(); 

Iterating BinaryHeap (max-heap) elements

    // iterator doesnt guarantee the order of items
    println!("Iterating over BinaryHeap (max-heap):");
    for x in &bh {
        println!("{x}");
    }

Retrieving elements using peek and pop methods of BinaryHeap (max-heap)

    // Peek method used to get greatest item in the BinaryHeap (Max-Heap)
    if let Some(t) = bh.peek() {
        println!("Greatest item from BinaryHeap (max-heap): {}", t);
    }

    // pop method returns items from max to min items
    println!("Loop through BinaryHeap (max-heap) and retrieve element using pop method:");
    while let Some(top) = bh.pop() {
        println!("Retrieving element using pop() method from BinaryHeap (max-heap): {top}");
    }    

BinaryHeap (as min-heap) code examples

Creating new BinaryHeap (min-heap) using new constructor method

    // Create new BinaryHeap (Min-Heap)
    let mut bh3 = BinaryHeap::new();
    bh3.push(core::cmp::Reverse(10));
    bh3.push(core::cmp::Reverse(20));
    bh3.push(core::cmp::Reverse(30));
    bh3.push(core::cmp::Reverse(40));
    bh3.push(core::cmp::Reverse(50));

Creating new BinaryHeap (min-heap) using From trait's from method

    // Creating BinaryHeap (Min-Heap) using From trait
    let bh4 = BinaryHeap::from([
        core::cmp::Reverse(1),
        core::cmp::Reverse(2),
        core::cmp::Reverse(3),
        core::cmp::Reverse(4),
        core::cmp::Reverse(5),
    ]);

Creating new BinaryHeap (min-heap) using IntoIterator trait's collect method

    // Creating BinaryHeap (Min-Heap) using IntoInterator trait
    let bh5: BinaryHeap<core::cmp::Reverse<i32>> = vec![
        core::cmp::Reverse(1),
        core::cmp::Reverse(2),
        core::cmp::Reverse(3),
        core::cmp::Reverse(4),
        core::cmp::Reverse(5),
    ]
    .into_iter()
    .collect();

Iterating BinaryHeap (min-heap) elements

    // iterator doesnt guarantee the order of items
    for x in &bh5 {
        println!("Element from BinaryHeap (min-heap) {:?}", x);
    }

Retrieving elements using peek and pop methods of BinaryHeap (min-heap)

    // Peek method used to get greatest item in the BinaryHeap (Min-Heap)
    if let Some(t) = bh3.peek() {
        println!("Greatest item from BinaryHeap (min-heap): {:?}", t);
    }

    // pop method returns items from min to max items
    while let Some(top) = bh3.pop() {
        println!(
            "Retrieving element using pop() method from BinaryHeap (min-heap): {:?}",
            top
        );
    }  

DSL operations on BinaryHeap

Some of the useful DSL operations that can be performed on BinaryHeap as below

sum method on BinaryHeap through Iterator trait

    // Finding sum of all elements
    println!(
        "Sum of all elements from BinaryHeap: {}",
        bh1.iter().sum::<i32>()
    );

product method on BinaryHeap through Iterator trait

    // Finding product of all elements
    println!(
        "Product of all elements from BinaryHeap: {}",
        bh1.iter().product::<i32>()
    );

zip method on BinaryHeap through Iterator trait

    // Merge 2 different vector and create Tuple object
    let j = vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1];
    let t = bh1.iter().zip(j.iter());
    t.for_each(|x| println!("Zipped Vector with BinaryHeap: {:?} ", x));

Create another type out from BinaryHeap

It is possible to create completely different type out from BinaryHeap using Iterator trait's collect method

Create HashMap type from BinaryHeap

    // Following operation will create a HashMap with each VecDeque element as Key and len as Value
    let mut s: BinaryHeap<&str> = BinaryHeap::new();
    s.push("Rust");
    s.push("is");
    s.push("awesome");
    let hm1: HashMap<_, _> = s.iter().map(|x| (x, x.len())).collect();
    println!("Created HashMap out from BinaryHeap: {:?}", hm1);

All the code examples can be found in this link

Please feel free to share your feedback.

Happy reading!!!