2
\$\begingroup\$

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 }
}
\$\endgroup\$
0

2 Answers 2

3
\$\begingroup\$

Formatting

Your current code is hard to read. The indentation of e.g. the trait bounds seems weird to me. Also the indentation and extra newlines in Heap::new() seems off to me. You can format your code accoring to the standard code style guidelines using cargo fmt or rustfmt respectively.

Unnecessary trait bounds

You require PartialEq and PartialOrd as trait bounds. But PartialOrd implies PartialEq. Therefore, the trait bound PartialEq is superfluous.

Furthermore, the trait bound to Copy is a rather heavy restriction. Consider relaxing it to Clone and call T.clone() explicitly where necessary.

Useless use of match

match self.max {} seems like overkill. match is intended for structural pattern matching. Since self.max is a bool a plain old if self.max {} else {} would suffice.

API design

You only use self.max in insert() and heapify(). Consider removing it as a struct member and making it a method parameter instead. This would also allow for new_empty() to be replaced by an appropriate implementation of Default.

I.e.:

use std::fmt::Debug;

pub struct Heap<T, D> {
    data: Option<Vec<(T, Option<Box<D>>)>>,
}

impl<T, D> Heap<T, D>
where
    T: Clone + PartialOrd + Debug,
    D: Clone + Debug,
{
    pub fn new(value: T, data: Option<Box<D>>) -> Self {
        Self {
            data: Some(vec![(value, data)]),
        }
    }

    pub fn is_empty(&self) -> bool {
        self.data.is_none()
    }

    // ...

    pub fn insert(
        &mut self,
        value: T,
        data: Option<Box<D>>,
        max: bool,
    ) -> 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)?;

        if max {
            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;
                }
            }
        } else {
            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(())
    }
}

impl<T, D> Default for Heap<T, D> {
    fn default() -> Self {
        Self { data: None }
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ Thank you for your return! It is really helpful. I have a question about the API design paragraph. I do not understand what you mean by “removing it as a struct member and making it a method parameter instead”. I believe (maybe wrongly) that those are method because I defined them in the "impl" of the struct. Could you please give me an example of what you mean? \$\endgroup\$
    – RomainL.
    Aug 28 at 15:10
  • \$\begingroup\$ Thank you for the Edit! \$\endgroup\$
    – RomainL.
    Aug 28 at 17:20
  • \$\begingroup\$ There is a very good reason to use max as a struct member (or generic parameter) though => it guarantees consistency. If insert is called half the time with max = true and the other half with max = false, you create a mess, not a heap. \$\endgroup\$ Sep 29 at 13:46
5
\$\begingroup\$

Unusual API

It's unusual for a heap API to be a key/value API, and even more unusual here is the fact that the "value" part is optional, so that some keys will be associated with a value, and others won't.

A more traditional API would be to take one element, and let the user create a struct implementing PartialEq/PartialOrd taking only a subset of fields into account as appropriate to their use-case.

Note: it's also VERY weird to force the value to be boxed, I'd never use a collection which forces me to allocate for each value.... imagine if I wanted to store a u8 there???

Why Option<Vec<...>>?

What's the difference between None and Some(vec![]), semantically, for your heap?

It's unlikely there's any, and therefore the Option<...> layer around Vec is strictly superfluous.

Note that Vec::new(), which creates an empty vector, does not allocate. In fact, it's even const thanks to not allocating.

Min/Max

The Rust standard library provides the Reverse type. Wrapping a value in Reverse reverses its </> operators.

Hence, given a MaxHeap<T>, defining a MinHeap<T> is essentially just as simple as:

type MinHeap<T> = MaxHeap<Reverse<T>>;

As such, the min/max parameter is somewhat superfluous. The user can already go from min to max or max to min easily enough.

Unusual bounds

Idiomatic Rust code tends to avoid bounds on code that doesn't need them.

There's no need for the element to be PartialOrd in the new method, nor in is_empty or len or capacity, nor in peek, ...

It's typical to create several impl blocks, with various sets of bounds.

Unusual new

In the standard library, the new method typically creates an empty collection. So should yours.

As a bonus, new could then be const.

Note: also consider a with_capacity constructor, to allow creating a heap with the right capacity, and avoid consecutive reallocations.

Unusual get_size

In the standard library, the number of elements in a collection is returned by the len method.

Unusual organization

In general, I would advise putting the pub items/methods at the top of the file, and the "helper" items/methods towards the bottom.

I would also advise putting the simple methods (new, is_empty, len, capacity, peek, ...) towards the top, and the more complex methods below, so the user can get a quicker overview of available methods.

No documentation

Your public items and methods should have documentation ///.

Most notably, on collection, I'd want to know:

  1. If a method may or may not lead to a memory allocation, and if yes under which circumstances.
  2. If a method may panic, under which circumstances it may do so.
  3. What is the algorithm complexity in time/space of the call.
  4. Possibly, what are related methods, when multiple methods have somewhat similar/opposite goals.
  5. Example usage code can be nice, and doubles as test too.

No test

Speaking of tests, I don't see any.

For collections, I'd really advise setting up some fuzzing tests. For a heap, for example:

  • I'd generate a vector of N elements from 0 to N-1.
  • I'd randomly shuffle that vector.
  • I'd create a new heap, and feed it the vector elements.
  • I'd then create a new vector by popping the elements one by one.
  • I'd check that the resulting vector is sorted (ascending or descending, accordingly).

Iteration

Your code is missing iterator support, which is perhaps the single most important piece to be a useful collection in the Rust ecosystem.

Specifically, you'll want:

  • To implement FromIterator and Extend, so the heap can be constructed/extended from all the elements of an iterator.
  • To implement IntoIterator, so the heap can be "deconstructed" into an iterator yields its elements.

Those are the basics for a collection.

You may not want to implement just "browsing", though, as there should be no need for a user to peek into the heap internal structure.

Revised API

/// A Max Heap.
///
/// To use as a Min Heap instead, wrap your elements in `std::cmp::Reverse`.
#[derive(Clone, Debug)]
pub struct MaxHeap<T>;

impl<T> MaxHeap<T> {
    /// Creates a new, empty, instance.
    pub const fn new() -> Self;

    /// Creates a new, empty, instance with the capacity for at least the specified
    /// number of elements.
    pub fn with_capacity(cap: usize) -> Self;

    /// Returns whether there is an element in the heap, or not.
    pub fn is_empty(&self) -> bool;

    /// Returns the number of elements in the heap.
    pub fn len(&self) -> usize;

    /// Returns the number of elements the heap may contain without any reallocation.
    pub fn capacity(&self) -> usize;

    /// Reserves capacity for `additional` more elements.
    ///
    /// After this call, `self.capacity() >= self.len() + additional`.
    ///
    /// This requires a memory allocation if `additional > self.capacity() - self.len()`.
    pub fn reserve(&mut self, additional: usize);

    /// Returns a reference to the top element, if any.
    pub fn peek(&self) -> Option<&T>;
}

impl<T> MaxHeap<T>
where
    T: PartialOrd,
{
    /// Pops the top element of the heap.
    ///
    /// # Algorithmic Complexity
    ///
    /// O(log N) in time, O(1) in space.
    pub fn pop(&mut self) -> Option<T>;

    /// Pushes an element in the heap.
    ///
    /// This requires a memory allocation if `self.len() == self.capacity()`.
    ///
    /// # Algorithmic Complexity
    ///
    /// O(log N) in time, O(1) in space.
    pub fn push(&mut self, element: T);
}

impl<T> Default for MaxHeap<T> {
    fn default() -> Self { Self::new() }
}

And Iterator compatibility:

impl<T> FromIterator<T> for MaxHeap<T> {
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = T>
    {
        //  -- Semi-naive implementation --
        let iter = iter.into_iter();

        let mut heap = Self::with_capacity(iter.size_hint().0);

        for element in iter {
            heap.push(element);
        }

        heap

        //  -- Optimized implementation --
        let mut heap = Self { data: Vec::from_iter(iter) };

        heap.heapify();

        heap
    }
}

impl<T> Extend<T> for MaxHeap<T> {
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = T>
    {
        //  -- Semi-naive implementation --
        let iter = iter.into_iter();

        //  Pre-reserving to avoid allocation in the loop.
        self.reserve(iter.size_hint().0);

        for element in iter {
            heap.push(element);
        }

        //  Not sure what an optimized implementation would look like;
        //  probably differs based on the ratio of existing elements and
        //  number of elements to insert.
    }
}

impl<T> IntoIterator for MaxHeap<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter(self)
    }
}

/// An Iterator over the elements of a `MaxHeap<T>`.
pub struct IntoIter<T>(MaxHeap<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }

    //  The following methods are provided as optimizations over the default
    //  implementations.

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.0.len(), Some(self.0.len())
    }

    fn count(self) -> usize {
        self.0.len()
    }
}

impl<T> ExactSizeIterator for IntoIter<T> {
    fn is_empty(&self) -> bool { self.0.is_empty() }

    fn len(&self) -> usize { self.0.len() }
}

//  A "fused" iterator is an iterator with a "fuse", that is an iterator which will
//  never again return an element after returning `None`.
impl<T> FusedIterator for IntoIter<T> {}

You may additionally provide a simple KeyValue helper:

/// A simple key value pair.
#[derive(Clone, Copy, Debug)]
pub struct KeyValue<K, V> {
    /// Key, on which the identity and ordering is based.
    pub key: K,
    /// Value, which does not participate to identity or ordering.
    pub value: V,
}

impl<K, V> PartialEq for KeyValue<K, V>
where
    K: PartialEq,
{
    fn eq(&self, other: &Self) -> bool { self.key.eq(&other.key) }
}

impl<K, V> PartialOrd for KeyValue<K, V>
where
    K: PartialOrd,
{
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.key.partial_cmp(&other.key)
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ thank you for the extensive review, there is a lot to chew for me and it is definitely very helpful! \$\endgroup\$
    – RomainL.
    Sep 30 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.