MinHeap.rs

use std::collections::binary_heap as max_heap;
use std::cmp::Reverse;
use std::ops::{Deref, DerefMut};

#[derive(Debug)]
struct MinHeap<T> {
    xheap: max_heap::BinaryHeap<Reverse<T>>,
}

impl<T: Ord> FromIterator<T> for MinHeap<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        MinHeap {
            xheap: iter.into_iter().map(|x| Reverse(x)).collect(),
        }
    }
}

impl<T: Ord> MinHeap<T> {
    fn new() -> Self {
        MinHeap {
            xheap: max_heap::BinaryHeap::new(),
        }
    }

    fn push(&mut self, x: T) {
        self.xheap.push(Reverse(x))
    }

    fn pop(&mut self) -> Option<T> {
        self.xheap.pop().map(|Reverse(x)| x)
    }

    fn peek(&self) -> Option<&T> {
        self.xheap.peek().map(|x| &x.0)
    }

    fn peek_mut(&mut self) -> Option<PeekMut<T>> {
        self.xheap.peek_mut().map(|inner| PeekMut { inner })
    }
}

struct PeekMut<'a, T: Ord> {
    inner: max_heap::PeekMut<'a, Reverse<T>>,
}

impl<T: Ord> Deref for PeekMut<'_, T> {
    type Target = T;

    fn deref(&self) -> &T {
        &self.inner.0
    }
}

impl<T: Ord> DerefMut for PeekMut<'_, T> {
    fn deref_mut(&mut self) -> &mut T {
        &mut self.inner.0
    }
}