You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
154 lines
2.8 KiB
154 lines
2.8 KiB
/*
|
|
heap
|
|
This question requires you to implement a binary heap function
|
|
*/
|
|
// I AM NOT DONE
|
|
|
|
use std::cmp::Ord;
|
|
use std::default::Default;
|
|
|
|
pub struct Heap<T>
|
|
where
|
|
T: Default,
|
|
{
|
|
count: usize,
|
|
items: Vec<T>,
|
|
comparator: fn(&T, &T) -> bool,
|
|
}
|
|
|
|
impl<T> Heap<T>
|
|
where
|
|
T: Default,
|
|
{
|
|
pub fn new(comparator: fn(&T, &T) -> bool) -> Self {
|
|
Self {
|
|
count: 0,
|
|
items: vec![T::default()],
|
|
comparator,
|
|
}
|
|
}
|
|
|
|
pub fn len(&self) -> usize {
|
|
self.count
|
|
}
|
|
|
|
pub fn is_empty(&self) -> bool {
|
|
self.len() == 0
|
|
}
|
|
|
|
pub fn add(&mut self, value: T) {
|
|
//TODO
|
|
}
|
|
|
|
fn parent_idx(&self, idx: usize) -> usize {
|
|
idx / 2
|
|
}
|
|
|
|
fn children_present(&self, idx: usize) -> bool {
|
|
self.left_child_idx(idx) <= self.count
|
|
}
|
|
|
|
fn left_child_idx(&self, idx: usize) -> usize {
|
|
idx * 2
|
|
}
|
|
|
|
fn right_child_idx(&self, idx: usize) -> usize {
|
|
self.left_child_idx(idx) + 1
|
|
}
|
|
|
|
fn smallest_child_idx(&self, idx: usize) -> usize {
|
|
//TODO
|
|
0
|
|
}
|
|
}
|
|
|
|
impl<T> Heap<T>
|
|
where
|
|
T: Default + Ord,
|
|
{
|
|
/// Create a new MinHeap
|
|
pub fn new_min() -> Self {
|
|
Self::new(|a, b| a < b)
|
|
}
|
|
|
|
/// Create a new MaxHeap
|
|
pub fn new_max() -> Self {
|
|
Self::new(|a, b| a > b)
|
|
}
|
|
}
|
|
|
|
impl<T> Iterator for Heap<T>
|
|
where
|
|
T: Default,
|
|
{
|
|
type Item = T;
|
|
|
|
fn next(&mut self) -> Option<T> {
|
|
//TODO
|
|
None
|
|
}
|
|
}
|
|
|
|
pub struct MinHeap;
|
|
|
|
impl MinHeap {
|
|
#[allow(clippy::new_ret_no_self)]
|
|
pub fn new<T>() -> Heap<T>
|
|
where
|
|
T: Default + Ord,
|
|
{
|
|
Heap::new(|a, b| a < b)
|
|
}
|
|
}
|
|
|
|
pub struct MaxHeap;
|
|
|
|
impl MaxHeap {
|
|
#[allow(clippy::new_ret_no_self)]
|
|
pub fn new<T>() -> Heap<T>
|
|
where
|
|
T: Default + Ord,
|
|
{
|
|
Heap::new(|a, b| a > b)
|
|
}
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
#[test]
|
|
fn test_empty_heap() {
|
|
let mut heap = MaxHeap::new::<i32>();
|
|
assert_eq!(heap.next(), None);
|
|
}
|
|
|
|
#[test]
|
|
fn test_min_heap() {
|
|
let mut heap = MinHeap::new();
|
|
heap.add(4);
|
|
heap.add(2);
|
|
heap.add(9);
|
|
heap.add(11);
|
|
assert_eq!(heap.len(), 4);
|
|
assert_eq!(heap.next(), Some(2));
|
|
assert_eq!(heap.next(), Some(4));
|
|
assert_eq!(heap.next(), Some(9));
|
|
heap.add(1);
|
|
assert_eq!(heap.next(), Some(1));
|
|
}
|
|
|
|
#[test]
|
|
fn test_max_heap() {
|
|
let mut heap = MaxHeap::new();
|
|
heap.add(4);
|
|
heap.add(2);
|
|
heap.add(9);
|
|
heap.add(11);
|
|
assert_eq!(heap.len(), 4);
|
|
assert_eq!(heap.next(), Some(11));
|
|
assert_eq!(heap.next(), Some(9));
|
|
assert_eq!(heap.next(), Some(4));
|
|
heap.add(1);
|
|
assert_eq!(heap.next(), Some(2));
|
|
}
|
|
} |