Rust Collections: BinaryHeap and its DSL Operations
Tags: rust
Published: 2023-01-11 14:29:00

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] (https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html) page from rust documentation.

##### BinaryHeap (as max-heap) code examples

###### Creating new BinaryHeap (max-heap) using `new` constructor method
```rust
    // 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
```rust
    // 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
```rust
    // 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
```rust
    // 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)
```rust
    // 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
```rust
    // 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
```rust
    // 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
```rust
    // 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
```rust
    // 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)
```rust
    // 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

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

##### `product` method on BinaryHeap through `Iterator` trait

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

##### `zip` method on BinaryHeap through `Iterator` trait

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

```rust
    // 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 ](https://github.com/sivakumar-sivaprakasam/rust-examples/tree/main/binaryheap)link

Please feel free to share your feedback.

Happy reading!!!