二項ヒープソートを使用する

二項ヒープソート (binomial heap sort) は、要素を二項ヒープへ挿入したあと、最小値を繰り返し取り出して昇順にする整列である。

二項ヒープは、次数（階数）の異なる二項木を根リストとして並べた森である。次数 k の二項木 B_k はちょうど 2^k 個の節点を持ち、根の子として B_{k-1}, B_{k-2}, …, B_0 が並ぶ。各木はヒープ条件（親のキーが子以下）を満たし、根リスト上では同じ次数の木は高々 1 本になるよう、マージ時に二進加算と同じ要領で結合する。

  1. 挿入: 各要素を次数 0 の木としてヒープへ加え、同じ次数の根があればキーの小さい方を親にして結合する。挿入 1 回は O(log n)、全体で O(n log n)。
  2. 抽出: 根リストから最小キーの根を外し、その子たちを逆順につないで別ヒープとみなし、残りと合併する。最小を 1 つ得るたびに O(log n)、n 回で O(n log n)。
  3. 書き戻し: 取り出したキーを配列の先頭から順に書けば昇順になる。
procedure link(y, z)
  // y.degree = z.degree かつ z.key <= y.key のとき、y を z の最左の子にする
  make y the leftmost child of z
  z.degree = z.degree + 1

procedure merge_roots(H1, H2)
  return root lists of H1 and H2 merged by increasing degree

procedure union(H1, H2)
  H = merge_roots(H1, H2)
  // 同じ次数が隣り合う根を link で畳み込み（二進加算の繰り上がり）
  consolidate equal-degree roots in H
  return H

procedure binomial_heap_sort(A)
  H = empty binomial heap
  for x in A
    H = union(H, singleton_tree(x))
  for i from 0 to length(A) - 1
    (min, H) = extract_min(H)
    A[i] = min

最悪時間計算量は O(n log n) で、節点用に O(n) の追加記憶域が要る（インプレースではない）。等値キーの相対順序は結合時の規約に依存し、一般に不安定である。二分ヒープを配列上で動かすヒープソートと比べ、ポインタ経由の合併はキャッシュ効率で劣りやすい一方、ヒープ同士の合併が自然に書ける点が優先度付きキューとしての強みになる。

優先度付きキューとして二項ヒープを使う場面では、複数ヒープの合併が二進数の加算に対応する点がそのままアルゴリズムの骨格になる。整列用途ではその合併を「すべて挿入してからすべて取り出す」形に固定したものが二項ヒープソートである。

類似アルゴリズムとの相違点

ヒープソートは配列上の二分ヒープをインプレースで縮める。

トーナメントソートも最小を繰り返し取り出すが、固定長のトーナメント木を更新する。

二分木ソートは探索木への挿入と中順走査で、ヒープ条件ではなく探索木条件を使う。

計算時間量および空間計算量を計測する

Size Average time Maximum time Average memory Maximum memory
256 0.000071 0.000221 98 104
512 0.000154 0.000324 158 164
1024 0.000350 0.000935 205 212
2048 0.000759 0.004242 194 200
4096 0.001698 0.029180 290 296
8192 0.003748 0.027801 502 508
16384 0.011507 0.036753 894 900
32768 0.026869 0.097900 1702 1708
65536 0.049441 0.165927 3330 3336
131072 0.126865 1.358980 6506 6536
262144 0.281175 0.961399 12842 12892
計測に使用したコードを表示する 

set -euo pipefail

WORKDIR="$(mktemp -d)"
trap 'rm -rf "$WORKDIR"' EXIT

cat > "$WORKDIR/Dockerfile" <<'EOF'
FROM rust:1.95.0

WORKDIR /app

RUN mkdir -p src

RUN cat > Cargo.toml <<'CARGO'
[package]
name = "rust-benchmark"
version = "0.1.0"
edition = "2021"

[profile.release]
lto = true
codegen-units = 1
panic = "abort"
CARGO

RUN cat > src/main.rs <<'RUST'
use std::{
    env,
    process::Command,
    time::{Duration, Instant},
};
const MIN_POWER: u32 = 8;
const MAX_POWER: u32 = 18;
const RUNS: usize = 8192;


struct BinomialNode {
    key: usize,
    degree: u32,
    child: Option<Box<BinomialNode>>,
    sibling: Option<Box<BinomialNode>>,
}

fn link(mut child: Box<BinomialNode>, mut parent: Box<BinomialNode>) -> Box<BinomialNode> {
    child.sibling = parent.child.take();
    parent.child = Some(child);
    parent.degree += 1;
    parent
}

fn roots_to_vec(mut head: Option<Box<BinomialNode>>) -> Vec<Box<BinomialNode>> {
    let mut roots = Vec::new();
    while let Some(mut node) = head.take() {
        head = node.sibling.take();
        roots.push(node);
    }
    roots
}

fn vec_to_roots(roots: Vec<Box<BinomialNode>>) -> Option<Box<BinomialNode>> {
    let mut head: Option<Box<BinomialNode>> = None;
    let mut tail = &mut head;
    for node in roots {
        *tail = Some(node);
        tail = &mut tail.as_mut().unwrap().sibling;
    }
    head
}

fn merge_root_lists(
    mut a: Option<Box<BinomialNode>>,
    mut b: Option<Box<BinomialNode>>,
) -> Option<Box<BinomialNode>> {
    let mut merged = Vec::new();
    while a.is_some() && b.is_some() {
        if a.as_ref().unwrap().degree <= b.as_ref().unwrap().degree {
            let mut node = a.take().unwrap();
            a = node.sibling.take();
            merged.push(node);
        } else {
            let mut node = b.take().unwrap();
            b = node.sibling.take();
            merged.push(node);
        }
    }
    while let Some(mut node) = a.take() {
        a = node.sibling.take();
        merged.push(node);
    }
    while let Some(mut node) = b.take() {
        b = node.sibling.take();
        merged.push(node);
    }
    vec_to_roots(merged)
}

fn consolidate(head: Option<Box<BinomialNode>>) -> Option<Box<BinomialNode>> {
    let mut roots = roots_to_vec(head);
    let mut i = 0;
    while i + 1 < roots.len() {
        if roots[i].degree != roots[i + 1].degree {
            i += 1;
            continue;
        }
        // Three equal degrees: leave the first and merge the latter two (CLRS).
        if i + 2 < roots.len() && roots[i + 2].degree == roots[i].degree {
            i += 1;
            continue;
        }
        let a = roots.remove(i);
        let b = roots.remove(i);
        let linked = if a.key <= b.key {
            link(b, a)
        } else {
            link(a, b)
        };
        roots.insert(i, linked);
    }
    vec_to_roots(roots)
}

fn union(
    h1: Option<Box<BinomialNode>>,
    h2: Option<Box<BinomialNode>>,
) -> Option<Box<BinomialNode>> {
    consolidate(merge_root_lists(h1, h2))
}

fn insert_key(heap: Option<Box<BinomialNode>>, key: usize) -> Option<Box<BinomialNode>> {
    let node = Box::new(BinomialNode {
        key,
        degree: 0,
        child: None,
        sibling: None,
    });
    union(heap, Some(node))
}

fn reverse_children(mut child: Option<Box<BinomialNode>>) -> Option<Box<BinomialNode>> {
    let mut rev: Option<Box<BinomialNode>> = None;
    while let Some(mut node) = child.take() {
        child = node.sibling.take();
        node.sibling = rev;
        rev = Some(node);
    }
    rev
}

fn extract_min(heap: Option<Box<BinomialNode>>) -> (Option<usize>, Option<Box<BinomialNode>>) {
    let Some(head) = heap else {
        return (None, None);
    };

    let mut roots = roots_to_vec(Some(head));
    let mut min_i = 0;
    for i in 1..roots.len() {
        if roots[i].key < roots[min_i].key {
            min_i = i;
        }
    }

    let mut min_node = roots.remove(min_i);
    let key = min_node.key;
    let children = reverse_children(min_node.child.take());
    (Some(key), union(vec_to_roots(roots), children))
}

fn binomial_heap_sort(a: &mut [usize]) {
    let mut heap = None;
    for &key in a.iter() {
        heap = insert_key(heap, key);
    }
    for slot in a.iter_mut() {
        let (key, next) = extract_min(heap);
        heap = next;
        *slot = key.expect("binomial heap exhausted early");
    }
}


fn benchmark_sort(array: &mut [usize]) {

    binomial_heap_sort(array);

}

fn is_non_decreasing(a: &[usize]) -> bool {
    a.windows(2).all(|w| w[0] <= w[1])
}

fn same_multiset(a: &[usize], b: &[usize]) -> bool {
    if a.len() != b.len() {
        return false;
    }

    let mut left = a.to_vec();
    let mut right = b.to_vec();
    left.sort_unstable();
    right.sort_unstable();
    left == right
}

fn check_correctness_case(label: &str, mut input: Vec<usize>) {
    let original = input.clone();

    benchmark_sort(&mut input);

    if !is_non_decreasing(&input) {
        panic!("correctness case {}: output is not sorted", label);
    }

    if !same_multiset(&input, &original) {
        panic!("correctness case {}: elements were lost or added", label);
    }
}

fn few_unique_values(size: usize, unique: usize, seed: u64) -> Vec<usize> {
    let mut state = seed;

    (0..size)
        .map(|_| {
            state ^= state << 13;
            state ^= state >> 7;
            state ^= state << 17;
            (state as usize % unique) + 1
        })
        .collect()
}

fn run_correctness_checks() {
    check_correctness_case("empty", vec![]);
    check_correctness_case("single", vec![42]);
    check_correctness_case("duplicates", vec![3, 1, 3, 2, 1, 2]);
    check_correctness_case("sorted", vec![1, 2, 3, 4, 5]);
    check_correctness_case("reverse", vec![5, 4, 3, 2, 1]);
    check_correctness_case("all_equal", vec![7, 7, 7, 7]);
    check_correctness_case("skewed_range", vec![1_000_000, 2, 1_000_001, 1, 999_999]);
    // Static-buffer Grail skips the in-buffer build when key collection is sparse
    // (ideal_buffer = false). Exercising that path catches regressions in buffer gating.
    check_correctness_case(
        "few_keys_len16",
        vec![2, 2, 2, 2, 2, 2, 2, 2, 4, 3, 1, 2, 3, 4, 1, 4],
    );
    for seed in 0..32 {
        check_correctness_case(
            &format!("few_keys_len32_seed_{seed}"),
            few_unique_values(32, 4, seed),
        );
    }
}


fn shuffled(size: usize, seed: u64) -> Vec<usize> {
    let mut v: Vec<usize> = (1..=size).collect();

    let mut state = seed;

    for i in (1..size).rev() {
        state ^= state << 13;
        state ^= state >> 7;
        state ^= state << 17;

        let j = (state as usize) % (i + 1);

        v.swap(i, j);
    }

    v
}

fn memory_usage_kb() -> usize {
    // VmHWM (peak RSS, KiB). Reported memory subtracts a per-size baseline that only
    // holds the input array, so the table reflects auxiliary space during sorting.
    let contents = std::fs::read_to_string("/proc/self/status")
        .unwrap_or_default();

    for line in contents.lines() {
        if let Some(rest) = line.strip_prefix("VmHWM:") {
            let kb = rest
                .split_whitespace()
                .next()
                .unwrap_or("0")
                .parse::<usize>()
                .unwrap_or(0);

            return kb;
        }
    }

    0
}

fn micros(d: Duration) -> u128 {
    d.as_micros()
}

fn input_array(size: usize, seed: u64) -> Vec<usize> {
    shuffled(size, seed)
}

fn run_baseline(size: usize) -> usize {
    let _hold = input_array(size, 1);
    memory_usage_kb()
}

fn run_once(size: usize, seed: usize) -> (u128, usize) {
    let mut array = input_array(size, seed as u64);

    let start = Instant::now();

    benchmark_sort(&mut array);

    let elapsed = start.elapsed();
    let mem = memory_usage_kb();

    let expected: Vec<usize> = (1..=size).collect();
    if array != expected {
        panic!(
            "sort failed with seed {} for size {}",
            seed,
            size
        );
    }

    (micros(elapsed), mem)
}

fn run_baseline_child(args: &[String]) {
    let size = args[2].parse::<usize>().expect("invalid size");
    let mem = run_baseline(size);
    println!("{}", mem);
}

fn run_child(args: &[String]) {
    let size = args[2].parse::<usize>().expect("invalid size");
    let seed = args[3].parse::<usize>().expect("invalid seed");
    let (elapsed_us, mem) = run_once(size, seed);
    println!("{} {}", elapsed_us, mem);
}

fn main() {
    let args: Vec<String> = env::args().collect();
    if args.get(1).is_some_and(|arg| arg == "--baseline-once") {
        run_baseline_child(&args);
        return;
    }
    if args.get(1).is_some_and(|arg| arg == "--run-once") {
        run_child(&args);
        return;
    }

    run_correctness_checks();

    println!(
        "| {:>10} | {:>15} | {:>15} | {:>15} | {:>15} |",
        "Size",
        "Average time",
        "Maximum time",
        "Average memory",
        "Maximum memory"
    );

    println!(
        "|{:-<11}:|{:-<16}:|{:-<16}:|{:-<16}:|{:-<16}:|",
        "",
        "",
        "",
        "",
        ""
    );

    for power in MIN_POWER..=MAX_POWER {
        let size = 1usize << power;

        let baseline_output = Command::new(env::current_exe().expect("failed to find current executable"))
            .arg("--baseline-once")
            .arg(size.to_string())
            .output()
            .expect("failed to run benchmark baseline process");

        if !baseline_output.status.success() {
            panic!(
                "benchmark baseline process failed: {}",
                String::from_utf8_lossy(&baseline_output.stderr)
            );
        }

        let baseline_stdout = String::from_utf8(baseline_output.stdout)
            .expect("baseline process returned non-UTF-8 output");
        let baseline_mem = baseline_stdout
            .split_whitespace()
            .next()
            .expect("missing baseline memory usage")
            .parse::<usize>()
            .expect("invalid baseline memory usage");

        let mut total_time: u128 = 0;
        let mut max_time: u128 = 0;

        let mut total_mem: usize = 0;
        let mut max_mem: usize = 0;

        for seed in 1..=RUNS {
            let output = Command::new(env::current_exe().expect("failed to find current executable"))
                .arg("--run-once")
                .arg(size.to_string())
                .arg(seed.to_string())
                .output()
                .expect("failed to run benchmark child process");

            if !output.status.success() {
                panic!(
                    "benchmark child process failed: {}",
                    String::from_utf8_lossy(&output.stderr)
                );
            }

            let stdout = String::from_utf8(output.stdout)
                .expect("child process returned non-UTF-8 output");
            let mut fields = stdout.split_whitespace();
            let elapsed_us = fields
                .next()
                .expect("missing elapsed time")
                .parse::<u128>()
                .expect("invalid elapsed time");
            let mem = fields
                .next()
                .expect("missing memory usage")
                .parse::<usize>()
                .expect("invalid memory usage");

            total_time += elapsed_us;

            if elapsed_us > max_time {
                max_time = elapsed_us;
            }

            let aux_mem = mem.saturating_sub(baseline_mem);

            total_mem += aux_mem;

            if aux_mem > max_mem {
                max_mem = aux_mem;
            }
        }

        let avg_time = total_time / RUNS as u128;
        let avg_mem = total_mem / RUNS;

        println!(
            "| {:>10} | {:>15} | {:>15} | {:>15} | {:>15} |",
            size,
            format!("{}.{:06}", avg_time / 1_000_000, avg_time % 1_000_000),
            format!("{}.{:06}", max_time / 1_000_000, max_time % 1_000_000),
            avg_mem,
            max_mem
        );
    }
}
RUST

RUN cargo build --release

CMD ["./target/release/rust-benchmark"]
EOF

docker build -t rust-benchmark "$WORKDIR"
docker run --rm --init rust-benchmark