How do I implement a heap in Rust?

To implement a heap in Rust, you can use a binary heap for an efficient priority queue. Rust provides a standard library implementation with the BinaryHeap type, but you can also create a custom heap structure if you need more control.

Using std::collections::BinaryHeap

The simplest way is to use the BinaryHeap from the standard library:

use std::collections::BinaryHeap;

fn main() {
    // Create a new BinaryHeap
    let mut heap = BinaryHeap::new();

    // Push elements onto the heap
    heap.push(4);
    heap.push(1);
    heap.push(7);
    heap.push(3);

    // Pop elements off the heap in descending order
    while let Some(value) = heap.pop() {
        println!("{}", value);
    }
}

Key Points:

• The BinaryHeap stores elements in a max-heap order (largest element at the top).
• For a min-heap, you can store elements as negative values or use a custom type with Ord implementation.

Custom Heap Implementation

If you want to implement your own heap for learning or specific requirements, here's an example:

Min-Heap Implementation

pub struct Heap<T> {
    elements: Vec<T>,
}

impl<T: Ord> Heap<T> {
    // Create a new empty heap
    pub fn new() -> Self {
        Heap {
            elements: Vec::new(),
        }
    }

    // Insert an element into the heap
    pub fn push(&mut self, value: T) {
        self.elements.push(value);
        self.bubble_up(self.elements.len() - 1);
    }

    // Remove and return the smallest element
    pub fn pop(&mut self) -> Option<T> {
        if self.elements.is_empty() {
            return None;
        }
        let result = self.elements.swap_remove(0);
        if !self.elements.is_empty() {
            self.bubble_down(0);
        }
        Some(result)
    }

    // Peek at the smallest element without removing it
    pub fn peek(&self) -> Option<&T> {
        self.elements.get(0)
    }

    fn bubble_up(&mut self, mut index: usize) {
        while index > 0 {
            let parent = (index - 1) / 2;
            if self.elements[index] >= self.elements[parent] {
                break;
            }
            self.elements.swap(index, parent);
            index = parent;
        }
    }

    fn bubble_down(&mut self, mut index: usize) {
        let len = self.elements.len();
        loop {
            let left = 2 * index + 1;
            let right = 2 * index + 2;

            let mut smallest = index;

            if left < len && self.elements[left] < self.elements[smallest] {
                smallest = left;
            }
            if right < len && self.elements[right] < self.elements[smallest] {
                smallest = right;
            }
            if smallest == index {
                break;
            }
            self.elements.swap(index, smallest);
            index = smallest;
        }
    }
}

fn main() {
    let mut heap = Heap::new();

    // Insert elements
    heap.push(4);
    heap.push(1);
    heap.push(7);
    heap.push(3);

    // Peek at the smallest element
    println!("Smallest: {:?}", heap.peek());

    // Pop elements in ascending order
    while let Some(value) = heap.pop() {
        println!("{}", value);
    }
}

Explanation:

1. Structure: The Heap struct uses a Vec to store elements.
2. Operations:
   • push: Adds an element and reorders the heap by "bubbling up."
   • pop: Removes the smallest element and reorders by "bubbling down."
   • peek: Returns the smallest element without removing it.
3. Bubble Up: Ensures the heap property is maintained after adding an element.
4. Bubble Down: Ensures the heap property after removing the root element.

This implementation creates a min-heap. You can adjust it to create a max-heap by reversing the comparison logic (< to >). This custom heap is more educational and flexible for specific scenarios.