Heap Sort in Rust: Includes a min-heap implementation as well as the heap-sort algorithm in Rust. Does not use generics because I haven't learned those yet.

heap_sort.rs

struct MinHeap {
    store: Vec<i32>,
}

impl MinHeap {
	pub fn new() -> Self {
		MinHeap { store: vec![] }
	}

	fn right_idx(&self, parent: usize) -> Option<usize> {
		let right: usize = 2 * parent + 2;
		if right < self.store.len() {
			Some(right)
		} else {
			None
		}
	}

	fn left_idx(&self, parent: usize) -> Option<usize> {
		let left: usize = 2 * parent + 1;
		if left < self.store.len() {
			Some(left)
		} else {
			None
		}
	}

	fn parent_idx(&self, child: usize) -> Option<usize> {
		if child == 0 {
			None
		} else if child <= 2 {
			Some(0)
		}else {
			if child % 2 == 1 {
				Some((child - 1) / 2)
			} else {
				Some((child - 2) / 2)
			}
		}
	}

	fn last_idx(&mut self) -> usize {
		self.store.len() - 1
	}

	fn shift_up(&mut self, idx: usize) {
		match self.parent_idx(idx) {
			None => return,
			Some(par) => {
				if self.store[idx] < self.store[par] {
					self.swap(idx, par);
					self.shift_up(par);
				}
			}
		}
	}

	fn shift_down(&mut self, idx: usize) {
		match self.left_idx(idx) {
			None => return,
			Some(left) => {
				match self.right_idx(idx) {
					None => {
						if self.store[idx] > self.store[left] {
							self.swap(idx, left);
							self.shift_down(left);
						}
					}
					Some(right) => {
						let min = if self.store[left] > self.store[right] {
							right
						} else {
							left
						};
						if self.store[idx] > self.store[min] {
							self.swap(idx, min);
							self.shift_down(min);
						}
					}
				}
			}
		}
	}

	fn swap(&mut self, a: usize, b: usize) {
		let tmp = self.store[a];
		self.store[a] = self.store[b];
		self.store[b] = tmp;
	}

	pub fn insert(&mut self, item: i32) {
		self.store.push(item);
		let last = self.last_idx();
		self.shift_up(last);
	}

	pub fn insert_many(&mut self, items: &[i32]) {
		for i in 0..items.len() {
			self.insert(items[i]);
		}
	}

	pub fn remove_min(&mut self) -> Option<i32> {
		if self.store.len() == 0 {
			None
		} else {
			// swap the first and last values
			let last = self.last_idx();
			self.swap(0, last);
			// remove the last value
			let min = self.store.pop();
			// shift the first value down
			self.shift_down(0);
			// return the value
			min
		}
	}

	pub fn print(&self) {
		println!("{:?}", self.store);
	}

	pub fn is_empty(&self) -> bool {
		if self.store.len() > 0 {
			false
		} else {
			true
		}
	}
}

fn heap_sort(to_sort: &Vec<i32>) -> Vec<i32>{
	if to_sort.len() == 0 {
		vec![]
	} else if to_sort.len() == 1 {
		vec![to_sort[0]]
	} else {
		let mut heap = MinHeap::new();
		heap.insert_many(&to_sort[..]);
		let mut result = Vec::with_capacity(to_sort.len());
		loop {
			match heap.remove_min() {
				None => break,
				Some(min) => result.push(min),
			}
		}
		result
	}
}

fn test_heap() {
	let mut heap = MinHeap::new();
	heap.insert_many(&[13,6,5,3,1,8,7,2,4,9,10,11,12]);
	heap.print();
	println!("{:?}", heap.remove_min());
	println!("{:?}", heap.remove_min());
	println!("{:?}", heap.remove_min());
	println!("{:?}", heap.remove_min());
	println!("{:?}", heap.remove_min());
	println!("{:?}", heap.remove_min());
	println!("{:?}", heap.remove_min());
	println!("{:?}", heap.remove_min());
	heap.print();
}

fn test_heap_sort() {
	let to_sort = &vec![];
	assert_eq!(heap_sort(to_sort), vec![]);

	let to_sort = &vec![1,2];
	assert_eq!(heap_sort(to_sort), vec![1,2]);

	let to_sort = &vec![2,1];
	assert_eq!(heap_sort(to_sort), vec![1,2]);

	let to_sort = &vec![1];
	assert_eq!(heap_sort(to_sort), vec![1]);

	let to_sort = &vec![6,5,3,1,8,7,2,4];
	assert_eq!(heap_sort(to_sort), vec![1,2,3,4,5,6,7,8]);

	let to_sort = &vec![6,5,3,1,8,7,2,4,9,10,11,12,13];
	assert_eq!(heap_sort(to_sort), vec![1,2,3,4,5,6,7,8,9,10,11,12,13]);

	println!("All sorting tests passed!");
}

fn main() {
    println!("Hello, world!");

    test_heap();
    test_heap_sort();
}