I am more on data analyst than a programmer, but I do enjoy coding for fun. I tried to implement a Heap in rust. I would appreciate any return you may have, so I can improve.
//! a minimal heap implementation support minimum and maximum heap, insertion,
//! heapify and pop/peeks at the top node.
//! Support optional data attached to a node
#[derive(Debug)]
///
/// T is a numeric value used to sort the heap
/// D is the attached type, if max is true the heap is maximum heap else it is minimum heap
///``` rust
/// let mut my_heap = Heap::new(5, Some(Box::new("chocolate")), false);
/// ```
pub struct Heap<T, D>{ data: Option<Vec<(T, Option<Box<D>>)>>, max: bool}
impl <T, D> Heap<T, D> where T: PartialEq + Copy + std::cmp::PartialOrd + std::fmt::Debug,
D: std::fmt::Debug + Copy, {
/// create a new non empty heap
///``` rust
/// let mut my_heap = Heap::new(5, Some(Box::new("chocolate")), false);
/// // or
/// let mut my_heap<i32, &str> = Heap::new(5, None, false);
/// ```
pub fn new(value: T, data: Option<Box<D>>,
max: bool) -> Self {
Heap{data: Some(vec![(value, data)]), max }
}
pub fn new_empty(max: bool) -> Self {
Heap{data: None, max }
}
pub fn is_empty(&self) -> bool{
match &self.data{
Some(_x) => false,
_ => true
}
}
/// swap 2 values from the heap
fn swap(&mut self, x: usize, y: usize) -> Result<(), &'static str> {
if self.is_empty(){
return Err("can't swap value of an empty heap");
}
let heap_size = self.get_size()?;
if (heap_size <= x) | (heap_size <= y){
return Err("swapping indice are out of index");
}
match self.data{
Some(ref mut data) => {
let p = data[x].clone();
data[x] = data[y].clone();
data[y] = p;
return Ok(());
},
_ => {return Err("error unwrapping heap while swapping");}
};
//let p = self.data[x].clone();
//self.data[x] = self.data[y].clone();
// self.data[y] = p;
//()
}
/// insert a new values in the heap
///``` rust
/// let mut my_heap = Heap::new(5, Some(Box::new("chocolate")), true);
/// result.insert(8, Some(Box::new("beast")));
/// result.insert(2, None);
///```
pub fn insert(&mut self, value: T, data: Option<Box<D>>) -> Result<(), &'static str>{
if self.is_empty(){
self.data.as_mut().unwrap().push((value, data));
return Ok(());
}
self.data.as_mut().unwrap().push((value, data));
let mut current_index = self.get_size()? - 1;
let mut parent = self.get_parent(current_index)?;
match self.max{
false => {
while parent.1 > value{
self.swap(current_index, parent.0)?;
current_index = parent.0;
if current_index != 0{
parent = self.get_parent(current_index)?;}
else{break}
}
},
true => {
while parent.1 < value{
self.swap(current_index, parent.0)?;
current_index = parent.0;
if current_index != 0{
parent = self.get_parent(current_index)?;}
else{break}
}
}
}
Ok(())
}
/// return a tuple, cloned value T / data D of the top node.
pub fn peeks_top(&self) -> Result<(T, Option<Box<D>>), &'static str>{
if self.is_empty(){
return Err("can't peeks at an empty heap");
}
match &self.data{
Some(data) => Ok((data[0].0, data[0].1.clone())),
_ => return Err("unwrapping while peeking")
}
//Ok((self.data.unwrap()[0].0, self.data.unwrap()[0].1.clone()))
}
fn heapify(&mut self, indice: usize) -> Result<(), &'static str>{
if self.is_empty(){
return Err("can't heapify empty Heap");
}
let length_heap = self.get_size()?;
println!("{} {}", indice, length_heap);
let mut should_be_on_top = indice;
let l = Self::get_left_child(indice);
let r = Self::get_right_child(indice);
match self.max{
true => {
if r < length_heap{
if self.data.as_ref().unwrap()[r].0 > self.data.as_ref().unwrap()[should_be_on_top].0{
should_be_on_top = r
}
}
if l < length_heap {
if self.data.as_ref().unwrap()[l].0 > self.data.as_ref().unwrap()[should_be_on_top].0 {
should_be_on_top = l
}
}
},
false => {
if r < length_heap {
if self.data.as_ref().unwrap()[r].0 < self.data.as_ref().unwrap()[should_be_on_top].0{
should_be_on_top = r
}
}
if l < length_heap {
if self.data.as_ref().unwrap()[l].0 < self.data.as_ref().unwrap()[should_be_on_top].0{
should_be_on_top = l
}
}
}
}
if should_be_on_top != indice{
self.swap(indice, should_be_on_top);
self.heapify(should_be_on_top);
}
Ok(())
}
pub fn get_size(&self) -> Result<usize, &'static str>{
if self.is_empty(){
return Err("empty Heap has no size");
}
Ok(self.data.as_ref().unwrap().len())
}
/// remove the top node from the heap, heapify the heap. Finaly, return the tuple (value<T>/data<D>) from the removed top node
pub fn pop(&mut self) -> Result<(T, Option<Box<D>>), &'static str>{
self.swap(0, self.get_size()? - 1)?;
let popped = self.data.as_mut().unwrap().pop();
self.heapify(0);
match popped{
Some(x) => Ok(x),
_ => return Err("error unwrapping after pop and heapify")
}
}
fn get_parent(&self, position: usize) -> Result<(usize, T), &'static str>{
if self.is_empty(){
return Err("no parent in empty Heap");
}
let x = (position - 1) / 2;
Ok((x, self.data.as_ref().unwrap()[x].0))
}
fn get_left_child(indice: usize) -> usize { indice * 2 + 1 }
fn get_right_child(indice : usize) -> usize{ indice * 2 + 2 }
}
