use crate::Error;
pub struct Heap<T> {
data: Vec<T>,
less: Box<dyn Fn(&T, &T) -> bool>,
}
impl<T: Clone> Heap<T> {
pub fn new(less: impl Fn(&T, &T) -> bool + 'static) -> Self {
Self {
data: Vec::new(),
less: Box::new(less),
}
}
pub fn len(&self) -> usize {
self.data.len()
}
pub fn is_empty(&self) -> bool {
self.data.is_empty()
}
pub fn push(&mut self, value: T) {
self.data.push(value);
self.sift_up(self.data.len() - 1);
}
pub fn pop(&mut self) -> Result<T, Error> {
if self.is_empty() {
return Err(Error::Empty);
}
if self.data.len() == 1 {
return Ok(self.data.pop().unwrap());
}
let root = self.data[0].clone();
self.data[0] = self.data.pop().unwrap();
self.sift_down(0);
Ok(root)
}
pub fn peek(&self) -> Result<&T, Error> {
self.data.first().ok_or(Error::Empty)
}
pub fn to_vec(&self) -> Vec<T> {
self.data.clone()
}
fn sift_up(&mut self, mut index: usize) {
while index > 0 {
let parent = (index - 1) / 2;
if (self.less)(&self.data[index], &self.data[parent]) {
self.data.swap(index, parent);
index = parent;
} else {
break;
}
}
}
fn sift_down(&mut self, mut index: usize) {
let len = self.data.len();
loop {
let mut target = index;
let left = 2 * index + 1;
let right = 2 * index + 2;
if left < len && (self.less)(&self.data[left], &self.data[target]) {
target = left;
}
if right < len && (self.less)(&self.data[right], &self.data[target]) {
target = right;
}
if target == index {
break;
}
self.data.swap(index, target);
index = target;
}
}
}
pub struct MinHeap<T: Ord + Clone> {
inner: Heap<T>,
}
impl<T: Ord + Clone> MinHeap<T> {
pub fn new() -> Self {
Self {
inner: Heap::new(|a, b| a < b),
}
}
pub fn len(&self) -> usize {
self.inner.len()
}
pub fn is_empty(&self) -> bool {
self.inner.is_empty()
}
pub fn push(&mut self, value: T) {
self.inner.push(value);
}
pub fn pop(&mut self) -> Result<T, Error> {
self.inner.pop()
}
pub fn peek(&self) -> Result<&T, Error> {
self.inner.peek()
}
pub fn to_vec(&self) -> Vec<T> {
self.inner.to_vec()
}
}
impl<T: Ord + Clone> Default for MinHeap<T> {
fn default() -> Self {
Self::new()
}
}
pub struct MaxHeap<T: Ord + Clone> {
inner: Heap<T>,
}
impl<T: Ord + Clone> MaxHeap<T> {
pub fn new() -> Self {
Self {
inner: Heap::new(|a, b| a > b),
}
}
pub fn len(&self) -> usize {
self.inner.len()
}
pub fn is_empty(&self) -> bool {
self.inner.is_empty()
}
pub fn push(&mut self, value: T) {
self.inner.push(value);
}
pub fn pop(&mut self) -> Result<T, Error> {
self.inner.pop()
}
pub fn peek(&self) -> Result<&T, Error> {
self.inner.peek()
}
pub fn to_vec(&self) -> Vec<T> {
self.inner.to_vec()
}
}
impl<T: Ord + Clone> Default for MaxHeap<T> {
fn default() -> Self {
Self::new()
}
}