Introduction

In Rust, BinaryHeap is a priority queue implemented with a binary heap. It allows you to maintain a dynamically sorted collection of elements where you can efficiently access and remove the largest element. This is particularly useful in algorithms that require repeatedly extracting the maximum element.

Using BinaryHeap

To use BinaryHeap, you need to import it from the std::collections module. You can create a BinaryHeap by using the BinaryHeap::new method. Elements can be added using push, and the largest element can be accessed and removed using peek and pop methods respectively.

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(5);
    heap.push(1);
    heap.push(10);

    println!("Peek: {:?}", heap.peek());
    println!("Pop: {:?}", heap.pop());
}
// Output:
// Peek: Some(10)
// Pop: Some(10)

Key Methods

Below are some of the key methods exposed by the BinaryHeap class:

BinaryHeap::new

Creates a new, empty BinaryHeap.

use std::collections::BinaryHeap;

fn main() {
    let heap = BinaryHeap::new();
    println!("Created an empty heap: {:?}", heap);
}
// Output:
// Created an empty heap: BinaryHeap([])

BinaryHeap::push

Adds an element to the BinaryHeap.

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(3);
    heap.push(7);
    println!("Heap after push: {:?}", heap);
}
// Output:
// Heap after push: BinaryHeap([7, 3])

BinaryHeap::pop

Removes and returns the largest element from the BinaryHeap. Returns None if the heap is empty.

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(4);
    heap.push(6);
    println!("Popped element: {:?}", heap.pop());
    println!("Heap after pop: {:?}", heap);
}
// Output:
// Popped element: Some(6)
// Heap after pop: BinaryHeap([4])

BinaryHeap::peek

Returns a reference to the largest element in the BinaryHeap, or None if it is empty.

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(8);
    println!("Peek element: {:?}", heap.peek());
}
// Output:
// Peek element: Some(8)

BinaryHeap::len

Returns the number of elements in the BinaryHeap.

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(2);
    heap.push(9);
    println!("Heap length: {}", heap.len());
}
// Output:
// Heap length: 2

Example Usage

Example 1: Basic Usage

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(12);
    heap.push(5);
    heap.push(8);

    println!("Heap: {:?}", heap);
}
// Output:
// Heap: BinaryHeap([12, 5, 8])

Example 2: Extracting Elements

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(20);
    heap.push(15);
    heap.push(30);

    println!("Extracted element: {:?}", heap.pop());
    println!("Remaining heap: {:?}", heap);
}
// Output:
// Extracted element: Some(30)
// Remaining heap: BinaryHeap([20, 15])

Example 3: Iterating Over Elements

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(7);
    heap.push(3);
    heap.push(9);

    for element in &heap {
        println!("{}", element);
    }
}
// Output:
// 9
// 3
// 7

Example 4: Creating from a Vector

use std::collections::BinaryHeap;

fn main() {
    let vec = vec![10, 5, 2, 7];
    let heap: BinaryHeap<_> = vec.into_iter().collect();
    println!("Heap from vector: {:?}", heap);
}
// Output:
// Heap from vector: BinaryHeap([10, 7, 2, 5])

Example 5: Using with Custom Types

use std::collections::BinaryHeap;
use std::cmp::Ordering;

#[derive(Eq, PartialEq)]
struct Item {
    value: i32,
}

impl Ord for Item {
    fn cmp(&self, other: &Self) -> Ordering {
        other.value.cmp(&self.value)
    }
}

impl PartialOrd for Item {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(Item { value: 1 });
    heap.push(Item { value: 5 });
    heap.push(Item { value: 3 });

    println!("Max item: {:?}", heap.pop().unwrap().value);
}
// Output:
// Max item: 5

Considerations

BinaryHeap does not provide sorted order traversal, it only provides the largest element efficiently.
The elements in the heap must implement the Ord trait.
For minimum heap, you can use Reverse wrapper on your values.