Rust Collections: BinaryHeap and its DSL Operations
Sivakumar
Posted on January 11, 2023
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!!!
💖 💪 🙅 🚩
Sivakumar
Posted on January 11, 2023
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
