MaxHeap practice...

main.rs

use std::mem::{swap};
use std::fmt::{Debug};

struct MaxHeap<T> {
  inner: Vec<T>
}

impl<T> MaxHeap<T> where T: PartialOrd<T> + Debug {
  #[inline]
  fn new() -> MaxHeap<T> {
    MaxHeap { inner: Vec::new() }
  }

  #[inline]
  fn top(&self) -> Option<&T> {
    self.inner.get(0)
  }

  fn pop(&mut self) -> Option<T> {
    if self.len() == 0 {
      None
    } else {
      println!("{:?}", self.inner);
      let item = self.inner.swap_remove(0);
      self.reheapify_down();
      Some(item)
    }
  }

  fn insert(&mut self, item: T) {
    self.inner.push(item);
    self.reheapify()
  }

  fn reheapify(&mut self) {
    if self.len() > 1 {
      println!("==Reaheapify Up==");

      let mut last_index: usize = self.len() - 1;

      loop {
        let parent_index = (last_index as f64 / 2 as f64).ceil() as usize - 1;

        println!("Testing {:?} against {:?}", last_index, parent_index);

        if &self.inner[last_index] > &self.inner[parent_index] {
          println!("Swapping {:?} with {:?}", last_index, parent_index);

          let last = unsafe { &mut *(&self.inner[last_index] as *const T as *mut T) };
          let parent = unsafe { &mut *(&self.inner[parent_index] as *const T as *mut T) };

          println!("Before: {:?}", self.inner);

          swap(last, parent);

          println!("After : {:?}", self.inner);

          last_index = parent_index;

          if last_index == 0 { break; }
        } else {
          break;
        }
      }
    }
  }

  fn reheapify_down(&mut self) {
    if self.len() > 1 {
      println!("==Reaheapify Down==");

      let mut current = 0;

      loop {
        let left_child = self.inner.get(current * 2 + 1);
        let right_child = self.inner.get((current + 1) * 2);

        match self.inner.get(current) {
          Some(n) => {
            match left_child {
              // Left child is bigger than the value at the current node.
              Some(n0) if n0 > n => {
                match right_child {
                  // Right child is bigger than left child...defer swapping to right child.
                  Some(n1) if n1 > n0 => (),
                  // Left child is equal to or greater than the right child, or there 
                  // is no right child...Perform swap
                  _ => {
                    println!("Swapping {:?} with {:?}", current, current * 2 + 1);

                    unsafe {
                      swap(
                        &mut *(left_child.unwrap() as *const T as *mut T),
                        &mut *(self.inner.get(current).unwrap() as *const T as *mut T));
                    }

                    current = current * 2 + 1;

                    continue;
                  }
                }
              }
              _ => ()
            }

            match right_child {
              // Right child is bigger than current (we already know here that the left
              // child must be smaller than this child otherwise the swap would've occured 
              // above).
              Some(n0) if n0 > n => {
                println!("Swapping {:?} with {:?}", current, (current + 1) * 2);

                unsafe {
                  swap(
                    &mut *(right_child.unwrap() as *const T as *mut T),
                    &mut *(self.inner.get(current).unwrap() as *const T as *mut T));
                }

                current = (current + 1) * 2;

                continue;
              }
              _ => ()
            }

            // The value at the current node was bigger than both the right and the left 
            // children, therefore the heap already has an appropriate structure.
            break;
          },
          // Current was moved to the top, reheapify is finished...
          None => break
        }
      }
    }
  }

  #[inline]
  fn len(&self) -> usize {
    self.inner.len()
  }
}

#[cfg(test)] #[test]
fn test_insert() {
  let mut heap: MaxHeap<usize> = MaxHeap::new();

  heap.insert(5);
  heap.insert(3);

  assert_eq!(*heap.top().unwrap(), 5);

  heap.insert(15);

  assert_eq!(*heap.top().unwrap(), 15);

  heap.insert(4);

  assert_eq!(*heap.top().unwrap(), 15);

  heap.insert(27);
  heap.insert(30);
  heap.insert(15);
  heap.insert(40);

  assert_eq!(*heap.top().unwrap(), 40);
}

#[cfg(test)] #[test]
fn test_pop() {
  let mut heap: MaxHeap<usize> = MaxHeap::new();

  heap.insert(12);
  heap.insert(9);
  heap.insert(10);
  heap.insert(3);
  heap.insert(1);
  heap.insert(0);

  assert_eq!(heap.pop().unwrap(), 12);
  assert_eq!(heap.pop().unwrap(), 10);
  assert_eq!(heap.pop().unwrap(), 9);
  assert_eq!(heap.pop().unwrap(), 3);
  assert_eq!(heap.pop().unwrap(), 1);
  assert_eq!(heap.pop().unwrap(), 0);
  assert!(heap.pop().is_none());
}