Table of content

Heapsort in Rust

Heapsort can be thought of as a deformation of the selection sort. It also divides the data into a sorted pile and an unsorted pile, and finds the maximum (or minimum) in the unsorted pile and adds it to the sorted pile.

Unlike the selection sort, the heapsort uses a heap of partially sorted data structures to aid and speed up sorting.

The characteristics of Heapsort are as follows:
  • Use the heap data structure to assist, usually using the binary heap.
  • Unstable ordering: After sorting, the relative position of elements of the same key value may change.
  • In-place sorting: no additional storage space to sort.
  • Poor CPU cache : The nature of the discontinuous access address of the heap is not conducive to CPU cache.
step

Heapsort's algorithm is divided into two major steps:

  • Convert the data to the heap data structure (max-heap for incremental sorting, min-heap for descending sorting).
  • Gradually take the maximum/minimum and replace it with the last element. Specific steps are as follows:
    1. Exchange the root of the heap with the last node, narrowing the scope of the heap (sorting a piece of data, so the length of the heap -1).
    2. Update the rest of the data to meet the characteristics of the heap, called the heap ordering property.
    3. Repeat the first two steps until the last unsorted material remains in the heap.

/// Heapsort.

pub fn heapsort(arr: &mut [i32]) {
    // -- Heapify part --
    // This procedure would build a valid max-heap.
    // (or min-heap for sorting descendantly)
    let end = arr.len();
    for start in (0..end / 2).rev() {
        // Skip leaf nodes (end / 2).
        sift_down(arr, start, end - 1);
    }

    // -- Sorting part --
    // Iteratively sift down unsorted part (the heap).
    for end in (1..arr.len()).rev() {
        arr.swap(end, 0);
        sift_down(arr, 0, end - 1);
    }
}

/// Internal function for heap to fix itself to conform to heap definition.

/// Precondiition: all elements below `start` are in heap order

/// expect `start` itself.

fn sift_down(arr: &mut [i32], start: usize, end: usize) {
    let mut root = start;
    loop {
        let mut child = root * 2 + 1; // Get the left child
        if child > end {
            break;
        }
        if child < end && arr[child] < arr[child + 1] {
            // Right child exists and is greater.
            child += 1;
        }

        if arr[root] < arr[child] {
            // If child is greater than root, swap'em!
            arr.swap(root, child);
            root = child;
        } else {
            break;
        }
    }
}

#[cfg(test)]

mod base {
    use super::*;
    base_cases!(heapsort);
}
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Subscribe to See Videos

Subscribe to my Youtube channel for new videos : Subscribe Now