Summary

• Intro
• Heap struct
• Insert
• Pop
• Heapsort
• Heapify
• Helpers
• Heap from vector

Intro

I've implemented the Heap data structure in rust language in this video. It's advisable to use BinaryHeap for most cases as it's production grade.

Heap struct

We start by defining our Heap data structure, which internally contains a vector.

pub struct Heap<T: Ord + Copy> {
    pub data: Vec<T>,
}

Insert

The insert algorithm will push an element at the end of our vector
and compare it with all the parents. If the parent is smaller (for a MaxHeap) or bigger (for a MinHeap), then we do the swap. In this way, everything gets ordered.

impl<T: Ord + Copy> Heap<T> {
    pub fn new() -> Self {
        Heap { data: vec![] }
    }

    pub fn insert(&mut self, element: T) {
        self.data.push(element);
        let mut last_element_idx = self.data.len() - 1;

        while last_element_idx != 0 {
            let parent_idx = self.parent(last_element_idx);

            if self.data[last_element_idx] > self.data[parent_idx] {
                self.data.swap(last_element_idx, parent_idx)
            }

            last_element_idx = parent_idx;
        }
    }

Pop

Removing an element from a Heap always starts at the root (the element in position 0 in our vector). The last piece from the array comes in its place. After that, we call the heapify function, which maintains the MaxHeap or MinHeap property.

    //...
    pub fn pop(&mut self) -> Option<T> {
        match self.data.len() {
            n if n == 0 => None,
            n if n == 1 => self.data.pop(),
            _ => {
                let last_element_idx = self.data.len() - 1;
                self.data.swap(0, last_element_idx);
                let value = self.data.pop().unwrap();

                self.heapify(0);

                Some(value)
            }
        }
    }

Heapsort

The heapsort works in the following manner: We will remove the element from the root by calling pop() and store it in an array. In this way, we will get every time the min or max element.

    pub fn into_sorted_vec(&mut self) -> Vec<T> {
        let mut vec = vec![];

        while self.data.len() > 0 {
            vec.push(self.pop().unwrap());
        }

        vec.reverse();

        vec
    }

Heapify

The heapify procedure has the role of maintaining the Heap property:

For every parent, both children should be less for a MaxHeap or greater for a MinHeap.

    fn heapify(&mut self, idx: usize) {
        let mut current = idx;

        loop {
            let left = self.left(current);
            let right = self.right(current);
            let size = self.data.len() - 1;

            if left > size || right > size {
                break;
            }

            let max = self.get_max_idx(left, right, current);

            if max != current {
                self.data.swap(current, max);

                current = max;
            } else {
                break;
            }
        }
    }

    fn get_max_idx(&self, left_idx: usize, right_idx: usize, idx: usize) -> usize {
        let max = self.data[left_idx]
            .max(self.data[right_idx])
            .max(self.data[idx]);

        match max {
            i if i == self.data[idx] => idx,
            i if i == self.data[right_idx] => right_idx,
            _ => left_idx,
        }
    }

Helpers

Helper functions that help to navigate the binary tree structure.

    fn parent(&self, idx: usize) -> usize {
        idx / 2
    }

    fn left(&self, idx: usize) -> usize {
        2 * idx + 1
    }

    fn right(&self, idx: usize) -> usize {
        2 * idx + 2
    }
}

Heap from Vector

To create a valid heap from a Vector, we can call the heapify function for all elements in reversed order.

As the binary tree structure will keep the children at the end of the vector, we need to traverse it bottom up to maintain the Heap Property.

impl<T: Ord + Copy> From<Vec<T>> for Heap<T> {
    fn from(data: Vec<T>) -> Self {
        let mut heap = Heap { data };

        for idx in (0..=heap.data.len() - 1).rev() {
            heap.heapify(idx)
        }

        heap
    }
}