heap Algorithm
Heap sort algorithm is a comparison-based sorting technique that utilizes a special data structure known as a binary heap. It is an in-place sorting algorithm, meaning that it doesn't require any additional memory to be allocated for temporary storage. Heap sort works by first building a binary heap (either a max-heap or a min-heap) from the input data, and then repeatedly extracting the maximum or minimum element from the heap and inserting it into a sorted array. This process continues until the heap becomes empty and the sorted array contains all the elements from the original input data.
A binary heap is essentially a complete binary tree with the property that each parent node is either greater than or equal to (in case of a max-heap) or less than or equal to (in case of a min-heap) its child nodes. Heap sort takes advantage of this property by ensuring that the largest or smallest element is always at the root of the heap, making it easy to extract and place in the sorted array. After extracting the root element, the algorithm restores the heap property by moving elements within the heap, a process called "heapifying". This "heapify" operation is repeated until the entire input data has been sorted. The time complexity of heap sort is O(n log n) in the worst, average, and best cases, making it an efficient and reliable sorting algorithm for various applications.
// Heap data structure
// Takes a closure as a comparator to allow for min-heap, max-heap, and works with custom key functions
use std::cmp::Ord;
use std::default::Default;
pub struct Heap<T>
where
T: Default,
{
count: usize,
items: Vec<T>,
comparator: Box<dyn Fn(&T, &T) -> bool>,
}
impl<T> Heap<T>
where
T: Default,
{
pub fn new(comparator: Box<dyn Fn(&T, &T) -> bool>) -> Self {
Self {
count: 0,
// Add a default in the first spot to offset indexes
// for the parent/child math to work out.
// Vecs have to have all the same type so using Default
// is a way to add an unused item.
items: vec![T::default()],
comparator,
}
}
pub fn len(&self) -> usize {
self.count
}
pub fn add(&mut self, value: T) {
self.count += 1;
self.items.push(value);
// Heapify Up
let mut idx = self.count;
while self.parent_idx(idx) > 0 {
let pdx = self.parent_idx(idx);
if (self.comparator)(&self.items[idx], &self.items[pdx]) {
self.items.swap(idx, pdx);
}
idx = pdx;
}
}
pub fn next(&mut self) -> Option<T> {
let next = if self.count == 0 {
None
} else {
// This feels like a function built for heap impl :)
// Removes an item at an index and fills in with the last item
// of the Vec
let next = self.items.swap_remove(1);
Some(next)
};
self.count -= 1;
if self.count > 0 {
// Heapify Down
let mut idx = 1;
while self.children_present(idx) {
let cdx = self.smallest_child_idx(idx);
if !(self.comparator)(&self.items[idx], &self.items[cdx]) {
self.items.swap(idx, cdx);
}
idx = cdx;
}
}
next
}
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 {
if self.right_child_idx(idx) > self.count {
self.left_child_idx(idx)
} else {
let ldx = self.left_child_idx(idx);
let rdx = self.right_child_idx(idx);
if (self.comparator)(&self.items[ldx], &self.items[rdx]) {
ldx
} else {
rdx
}
}
}
}
pub struct MinHeap;
impl MinHeap {
pub fn new<T>() -> Heap<T>
where
T: Default + Ord,
{
let comparator = |a: &T, b: &T| a < b;
Heap::new(Box::new(comparator))
}
}
pub struct MaxHeap;
impl MaxHeap {
pub fn new<T>() -> Heap<T>
where
T: Default + Ord,
{
let comparator = |a: &T, b: &T| a > b;
Heap::new(Box::new(comparator))
}
}
#[cfg(test)]
mod tests {
use super::*;
#[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));
}
struct Point(/* x */ i32, /* y */ i32);
impl Default for Point {
fn default() -> Self {
Self(0, 0)
}
}
#[test]
fn test_key_heap() {
let mut heap: Heap<Point> = Heap::new(Box::new(|a, b| a.0 < b.0));
heap.add(Point(1, 5));
heap.add(Point(3, 10));
heap.add(Point(-2, 4));
assert_eq!(heap.len(), 3);
assert_eq!(heap.next().unwrap().0, -2);
assert_eq!(heap.next().unwrap().0, 1);
heap.add(Point(50, 34));
assert_eq!(heap.next().unwrap().0, 3);
}
}
