A Weekly Rust🦀 Pill #4

A Weekly Rust🦀 Pill is a post series where on a weekly base, I share some implementations of the most popular algorithms and data structures to share my learnings on Rust 🦀.

Heap

In data structures, heaps play a crucial role in efficiently managing and organising data. A heap is a specialised tree-based data structure that satisfies the heap property, distinguishing it from other tree structures. Among the variations of heaps, the max heap stands out as an important and versatile structure with various applications in computer science.

Properties of a Max Heap:

A max heap is characterised by several key properties that make it a powerful tool for solving various computational problems:

Heap Property: The primary defining property of a max heap is the heap property. In a max heap, for any given node i, the value stored in i is greater than or equal to the values stored in its children. This property ensures that the maximum element is always at the root of the heap.

Shape Property: A max heap is a complete binary tree, meaning it is filled at all levels except possibly the last level, where nodes are filled from left to right. This structural property contributes to the efficient storage of elements in memory.

Max Element Access: As mentioned earlier, the maximum element is always at the root of the max heap. This property allows for quick access to the maximum element without the need to traverse the entire heap.

Efficient Insertion and Deletion: Max heaps offer efficient insertion and deletion operations while maintaining the heap property. Inserting an element involves placing it at the next available position in the heap and then "bubbling up" or "sifting up" the element to its correct position. Similarly, deleting the maximum element involves replacing it with the last element in the heap and then "bubbling down" or "sifting down" the element to its correct position.

Priority Queue Implementation: Max heaps are often used to implement priority queues, where elements are assigned priorities and operations are performed based on these priorities. The max heap property ensures that the element with the highest priority (i.e., the maximum value) is always at the front of the queue.

Sorting: Max heaps can be utilised in heapsort, a comparison-based sorting algorithm. The algorithm first constructs a max heap from the input data and then repeatedly extracts the maximum element from the heap, resulting in a sorted array.

Efficient k-Largest/K-Smallest Elements: Max heaps are particularly useful for finding the k-largest (or k-smallest) elements in a data collection. By repeatedly extracting the maximum element k times, you can efficiently determine the k-largest elements.

Implementations

Let's see the code:

struct Heap<T: Ord> {
    items: Vec<T>,
}

impl<T: Ord> Heap<T> {
    fn new() -> Self {
        Heap { items: vec![] }
    }

    /* Helper functions */
    fn parent(&self, i: usize) -> usize {
        i / 2
    }

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

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

    fn insert(&mut self, item: T) {
        self.items.push(item);

        let mut current_last_item_idx: usize = self.items.len() - 1;

        while current_last_item_idx != 0 {
            let parent_idx: usize = self.parent(current_last_item_idx);

            if self.items[current_last_item_idx] > self.items[parent_idx] {
                self.items.swap(current_last_item_idx, parent_idx);
            }

            current_last_item_idx = parent_idx
        }
    }

    fn pop(&mut self) -> Option<T> {
        match self.items.len() {
            0 => None,
            1 => self.items.pop(),
            _ => {
                let last_item_idx = self.items.len() - 1;
                self.items.swap(0, last_item_idx);
                let item = self.items.pop().unwrap();

                self.heapify(0);

                Some(item)
            }
        }
    }

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

        loop {
            let left: usize = self.left(current);
            let right: usize = self.right(current);
            let size: usize = self.items.len();

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

            let mut max = current;
            if self.items[current] < self.items[left] {
                max = left
            } else if self.items[current] < self.items[right] {
                max = right
            }

            if max != current {
                self.items.swap(current, max);
                current = max;
            } else {
                break;
            }
        }
    }
}

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

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

        heap
    }
}

To define a generic max heap we start wrapping up a vec<T> with a struct. Then the implementation (impl<T> Heap<T>) uses a generic type T to allow it to store any data. The Heap struct has four methods: new, parent, left, right, insert, pop, heapify and From.

a. fn new() -> Self This method creates and returns a new empty Heap.

b. Helper functions:

fn parent(&self, i: usize) -> usize This helper function calculates the index of the parent of the element at index i in the heap.

fn left(&self, i: usize) -> usize This helper function calculates the index of the left child of the element at index i in the heap.

fn right(&self, i: usize) -> usize This helper function calculates the index of the right child of the element at index i in the heap.

c. fn insert(&mut self, item: T) This method inserts a new item into the heap while maintaining the heap property. The new item is added to the end of the items vector, then compared with its parent and swapped upwards if it is greater than its parent.

d. fn pop(&mut self) -> Option<T> This method removes and returns the maximum (root) element from the heap. If the heap is empty, it returns None. If there's only one element, it is removed. Otherwise, the last element is swapped with the root, the root is removed, and the heap is adjusted to satisfy the heap property using the heapify function.

e. fn heapify(&mut self, position: usize) This method performs the "heapify" operation, which ensures that the subtree rooted at the element at the given position maintains the heap property. It compares the element at the current position with its children and swaps with the larger child if necessary, then continues this process recursively.

f. impl<T: Ord> From<Vec<T>> for Heap<T> This implementation allows creating of a heap from a vector of elements. The from function constructs a new heap by iterating through the vector in reverse order and calling heapify for each element to build a valid max heap.

References

• Heap introduction
• Heap implementation in Rust std library