Trait Heap

pub trait Heap<T> {
    // Required methods
    fn len(&self) -> usize;
    fn less(&self, i: usize, j: usize) -> bool;
    fn swap(&mut self, i: usize, j: usize);
    fn push(&mut self, x: T);
    fn pop(&mut self) -> T;
    fn peak(&self) -> Option<&T>;
}

All types which you want to create heap from them must implement this trait

Example of Min Heap

use go_heap_rs::Heap;
struct MinHeap(Vec<i32>);
impl Heap<i32> for MinHeap {
    fn len(&self) -> usize {
        self.0.len()
    }

    fn less(&self, i: usize, j: usize) -> bool {
        self.0[i] < self.0[j]
    }

    fn swap(&mut self, i: usize, j: usize) {
        self.0.swap(i, j);
    }

    fn push(&mut self, x: i32) {
        self.0.push(x);
    }

    fn pop(&mut self) -> i32 {
        self.0.pop().expect("pop on an empty vec!")
    }

    fn peak(&self) -> Option<&i32> {
        self.0.get(0)
    }
}

Required Methods

fn len(&self) -> usize

length must return the length of the heap

fn less(&self, i: usize, j: usize) -> bool

Compares two elements of the heap at i and j index It is guaranteed that the i and j are always valid

fn swap(&mut self, i: usize, j: usize)

This function must swap the i and j element in the heap array It is guaranteed that the i and j are always valid

fn push(&mut self, x: T)

push is just like push in vector. It should add x to the last of array

fn pop(&mut self) -> T

This method should remove the last element of array and return it This function is guaranteed to be called when at least one element in available

fn peak(&self) -> Option<&T>

This method must return first element in your collection

Implementors

impl<T: Ord> Heap<T> for MinHeap<T>