【Rust】ヒープソート

ヒープは木構造で構成され、子ノードは常に親ノードより大きいか等しい。
ヒープに要素を追加する場合は、木構造の最後に要素を追加し、親と要素を比較して親よりも小さければ親と交換する。
最小値は必ずルートにある。
取り出した場合は、最後の要素を一番上に移して木を再構成する。

木構造が
A
B C
D E F G
の時、リストでは
[ABCDEFG] で表現する。

fn main() {
    
    let mut data = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13];

    for i in 0..data.len() {
        let mut j = i;
        while ( j > 0 ) && (data[(j - 1) / 2] < data[j]) {
            data.swap(j, (j - 1) / 2);
            j = (j - 1) / 2;
        }
    }
    println!("{:?}", data);

    let mut n: Vec<usize> = Vec::new();
    for i in 1..(data.len()+1) {
        n.push(i.try_into().unwrap());
    }
    n.reverse();

    for i in n {
        data.swap(0, i - 1);
        let mut j = 0;
        while(((2 * j + 1) < (i - 1)) && (data[j] < data[2 * j + 1])) || (((2 * j + 2) < (i - 1)) && (data[j] < data[2 * j + 2])) {
            if ((2 * j + 2) == (i - 1)) || (data[2 * j + 1] > data[2 * j + 2]) {
                data.swap(2 * j + 1, j);
                j = 2 * j + 1;
            } else {
                data.swap(2 * j + 2, j);
                j = 2 * j + 2;
            } 
        }
    }
    println!("{:?}", data);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.37s
Running `target/debug/rust`
[15, 13, 11, 8, 9, 4, 5, 2, 7, 6]
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

ヒープの構成のところで、
15
13 11
8 9 4 5
2 7 6
と、ヒープの構成になっていることがわかる。
heap sortはbubble, insert, selection sortより早いことがわかっている。

関数化する。

use std::collections::VecDeque;

fn heapify(data: &mut VecDeque<usize>, i: usize) {
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let size = data.len() - 1;
    let mut min = i;
    if left <= size && data[min] > data[left] {
        min = left;
    }
    if right <= size && data[min] > data[right] {
        min = right;
    }
    if min != i {
        data.swap(min, i);
        heapify(data, min);
    }
}

fn main() {
    
    let mut data = VecDeque::from([6, 15, 4, 2, 8, 5, 11, 9, 7, 13]);

    let mut n: Vec<usize> = Vec::new();
    for i in 0..(data.clone().len()/2) {
        n.push(i.try_into().unwrap());
    }
    n.reverse();

    println!("{:?}", n);

    for i in n {
        heapify(&mut data, i);
    }
    println!("{:?}", data);

    let mut sorted_data: VecDeque<usize> = VecDeque::new();

    for _ in 0..(data.len()) {
        let k = data.clone().len();
        data.swap(0, k - 1);
        sorted_data.push_back(data.pop_back().unwrap());
        println!("{:?}", sorted_data);
        println!("{:?}", data);
        if (k != 1) {
            heapify(&mut data, 0);
        }
    }

    println!("{:?}", sorted_data);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.41s
Running `target/debug/rust`
[4, 3, 2, 1, 0]
[2, 6, 4, 7, 8, 5, 11, 9, 15, 13]
[2]
[13, 6, 4, 7, 8, 5, 11, 9, 15]
[2, 4]
[15, 6, 5, 7, 8, 13, 11, 9]
[2, 4, 5]
[9, 6, 11, 7, 8, 13, 15]
[2, 4, 5, 6]
[15, 7, 11, 9, 8, 13]
[2, 4, 5, 6, 7]
[13, 8, 11, 9, 15]
[2, 4, 5, 6, 7, 8]
[15, 9, 11, 13]
[2, 4, 5, 6, 7, 8, 9]
[15, 13, 11]
[2, 4, 5, 6, 7, 8, 9, 11]
[15, 13]
[2, 4, 5, 6, 7, 8, 9, 11, 13]
[15]
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
[]
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

ほう、これは凄いな。というか、debugしながらやらないと理解できない。。