堆排序

堆排序是一个in-place的O(n log n)的排序算法，它基于最大堆来实现，该最大堆本质上是一个二叉树数据结构，并且该二叉树的父节点总是大于或等于它的子节点。

最大堆的实现

最大堆最有效的实现方式是通过数组来实现。

二叉树与数组的呈现方式，如下图所示：

如果给定某个节点的索引为“i”，可以通过以下规则来计算其父索引和子索引：

• parent(i) = (i-1) / 2
• left_child(i) = 2*i + 1
• right_child(i) = 2*i + 2

算法实现

堆排序的实现有两步：

1. 把输入的数组转换为一个最大堆。
2. 将数组划分为堆部分（heap part）和排序部分（sorted part）。初始化时，堆部分（heap part）包含所有的数组，排序部分（sorted part）是空的。

重复地将堆的根(即最大的)节点与堆的最后一个节点交换，并将排序的部分增加一个节点，如下图所示：

每次交换后，修复堆使其再次成为有效的最大堆。

一旦堆为空，' arr '将被完全排序。

代码

• move_down

/// Move the element at `root` down until `arr` is a max heap again.
///
/// This assumes that the subtrees under `root` are valid max heaps already.
fn move_down<T: Ord>(arr: &mut [T], mut root: usize) {
    let last = arr.len() - 1;
    loop {
        let left = 2 * root + 1;
        if left > last {
            break;
        }
        let right = left + 1;
        let max = if right <= last && arr[right] > arr[left] {
            right
        } else {
            left
        };

        if arr[max] > arr[root] {
            arr.swap(root, max);
        }
        root = max;
    }
}

• heapify

/// Convert `arr` into a max heap.
fn heapify<T: Ord>(arr: &mut [T]) {
    let last_parent = (arr.len() - 2) / 2;
    for i in (0..=last_parent).rev() {
        move_down(arr, i);
    }
}

• heapSort

pub fn heap_sort<T: Ord>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return; // already sorted
    }

    heapify(arr);

    for end in (1..arr.len()).rev() {
        arr.swap(0, end);
        move_down(&mut arr[..end], 0);
    }
}

• Test

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn empty() {
        let mut arr: Vec<i32> = Vec::new();
        heap_sort(&mut arr);
        assert_eq!(&arr, &[]);
    }

    #[test]
    fn single_element() {
        let mut arr = vec![1];
        heap_sort(&mut arr);
        assert_eq!(&arr, &[1]);
    }

    #[test]
    fn sorted_array() {
        let mut arr = vec![1, 2, 3, 4];
        heap_sort(&mut arr);
        assert_eq!(&arr, &[1, 2, 3, 4]);
    }

    #[test]
    fn unsorted_array() {
        let mut arr = vec![3, 4, 2, 1];
        heap_sort(&mut arr);
        assert_eq!(&arr, &[1, 2, 3, 4]);
    }

    #[test]
    fn odd_number_of_elements() {
        let mut arr = vec![3, 4, 2, 1, 7];
        heap_sort(&mut arr);
        assert_eq!(&arr, &[1, 2, 3, 4, 7]);
    }

    #[test]
    fn repeated_elements() {
        let mut arr = vec![542, 542, 542, 542];
        heap_sort(&mut arr);
        assert_eq!(&arr, &vec![542, 542, 542, 542]);
    }
}