min_heap.rs

use std::marker::PhantomData;
use std::mem::swap;

//Min heap
struct MinHeap<T> {
    root: Option<Node<T>>,
    phantom_data: PhantomData<T>,
}

struct Node<T> {
    left: Option<RefCell<Node<T>>>,
    right: Option<RefCell<Node<T>>>,
    parent: Option<RefCell<Node<T>>>,
    elem: T,
    child_count: usize,
    phantom_data: PhantomData<T>,
}

impl<T> Node<T> {
    fn new(elem: T, parent: &Node<T>) -> Self {
        Self {
            left: None,
            right: None,
            elem: elem,
            parent: RefCell::new(parent),
            child_count: 0,
            phantom_data: PhantomData,
        }
    }
}

impl<T> MinHeap<T> {
    fn new() -> MinHeap<T> {
        MinHeap {
            root: None,
            phantom_data: PhantomData,
        }
    }

    fn get_min(&mut self) -> Option<T> {




        todo!();
    }

    //finds next node to insert element at
    fn down_propogate(node: &RefCell<Node>) -> &mut Node {
        if node.left == None || node.right == None {
            node.parent.unwrap().borrow_mut()
        } else if node.left.unwrap().child_count <= node.right.unwrap().child_count {
            node.left.unwrap().borrow_mut().child_count += 1;
            down_propogate(node.left.unwrap().borrow())
        } else {
            node.right.unwrap().borrow_mut().child_count += 1;
            down_propogate(node.right.unwrap().borrow())
        }
    }

    fn insert(&mut self, elem: T) {
        if self.root == None {
            self.root = RefCell::new(Node::new(elem));
            return;
        }
        //finds lowest node
        let &mut node = down_propogate(self.root).borrow_mut();
        node.child_count += 1;

        if node.left == None {
            node.left = Some(RefCell::new(Node::new(elem)));
        } else {
            node.right = Some(RefCell::new(Node::new(elem)));
        }

        //todo!();
    }

    //possibly rename to pop
    fn delete_min(&mut self) {
        todo!();
    }

    //...
}