Heap Sort

Heap

To code a heap_sort function, we need to implement the heap data structure on an array.

#![allow(unused)]
fn main() {
pub struct Heap<T> {
    buffer: Box<[T]>,
    size: usize,
}
}

Looks simple enough... now we need a way to create a heap (ideally from a boxed slice) or just create an empty one in which to insert values later.

#![allow(unused)]
fn main() {
impl<T: Copy + Ord> From<Box<[T]>> for Heap<T> {
    fn from(value: Box<[T]>) -> Self {
        let mut heap = Self {
            size: value.len(),
            buffer: value,
        };

        heap.build();
        heap
    }
}
}

We'll look into the specification of the Heap::build method later, to see what does it do, and why it requires Copy and Ord traits.

#![allow(unused)]
fn main() {
impl<T: Default + Copy> Heap<T> {
    pub fn new<const SIZE: usize>() -> Self {
        Self {
            buffer: Box::new([Default::default(); SIZE]),
            size: 0,
        }
    }
}
}

Heap Methods

heapify is the most important method to make a heap work: it basically rearranges in \(O(\log{n})\) a Heap in which only the root is out of order.

#![allow(unused)]
fn main() {
impl<T: Ord + Copy> Heap<T> {
    fn heapify(&mut self, node: usize) {
        use std::cmp::max;

        if let Some((v, i)) = max(self.child(node, 1), self.child(node, 2)) {
            if self.buffer.get(node) < v {
                self.buffer.swap(node, i);
                self.heapify(i)
            }
        }
    }
}
}

Now that we have the heapify method, to build the Heap, we just need to run heapify on the left side of the array.

#![allow(unused)]
fn main() {
impl<T: Ord + Copy> Heap<T> {
    fn build(&mut self) {
        (0..self.size / 2).rev().for_each(|n| self.heapify(n));
    }
}
}

Indexing a Heap

In a Heap, to get the children of a node at an index i, we just need a formula:

• i * 2 + 1 for the left child
• i * 2 + 2 for the right child

Knowing this, we can write a child method to get the children of a node in a Heap, and reuse it in the heapify method.

#![allow(unused)]
fn main() {
impl<T: Ord + Copy> Heap<T> {
    fn child(&self, node: usize, child: usize) -> Option<(Option<&T>, usize)> {
        let node = 2 * node + child;

        if node >= self.size {
            return None;
        }

        Some((self.buffer.get(node), node))
    }
}
}

Iterating a Heap

Now that we have the Heap setup, we just need to implement the Iterator trait to consume the Heap. The next method is very simple: we just swap the last element with the root (in position 0), reduce the size of the Heap, and run heapify again.

#![allow(unused)]
fn main() {
impl<T: Ord + Copy> Iterator for Heap<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.size == 0 {
            return None;
        }

        self.buffer.swap(0, self.size - 1);
        self.size -= 1;
        self.heapify(0);

        Some(self.buffer[self.size])
    }
}
}

Heap Sort

Now sorting a Heap becomes a very easy task! We just have to run heapify until the there are no more elements, and the unerlying buffer will be sorted.

#![allow(unused)]
fn main() {
pub fn heap_sort<T: Ord + Copy + Default>(buffer: Box<[T]>) {
    Heap::from(buffer).into_iter().for_each(drop);
}
}

Exercises

#![allow(unused)]
fn main() {
pub mod exercises {
    use std::cmp::Reverse;

    use super::*;

    // Ex 1, O(n) for MaxHeap, O(1) for MinHeap

    pub enum BinaryHeap<T> {
        MaxHeap(Heap<T>),
        MinHeap(MinHeap<T>),
    }

    pub fn min<T: Ord + Copy + Default>(heap: &mut BinaryHeap<T>) -> Option<T> {
        match heap {
            BinaryHeap::MaxHeap(heap) => heap.last(),
            BinaryHeap::MinHeap(heap) => heap.next(),
        }
    }

    // Ex 2, Build a MinHeap struct

    pub struct MinHeap<T> {
        heap: Heap<T>,
    }

    impl<T: Ord + Default + Copy> MinHeap<Reverse<T>> {
        pub fn from(buffer: Box<[T]>) -> Self {
            Self {
                heap: Heap::from(
                    buffer
                        .iter()
                        .map(|v| Reverse(*v))
                        .collect::<Vec<Reverse<T>>>()
                        .into_boxed_slice(),
                ),
            }
        }
    }

    impl<T: Ord + Default + Copy> Iterator for MinHeap<T> {
        type Item = T;

        fn next(&mut self) -> Option<Self::Item> {
            self.heap.next()
        }
    }

    // Ex 3, insert in Heap with available space

    impl<T: Ord + Default + Copy> Heap<T> {
        pub fn insert(&mut self, value: T) -> Result<(), &'static str> {
            if self.size >= self.buffer.len() {
                return Err("Array is full");
            }

            self.buffer[self.size] = value;
            self.size += 1;
            self.build();

            Ok(())
        }
    }
}
}