二項ヒープソートで配列を並び替える
二項ヒープソートを使用する
二項ヒープソート (binomial heap sort) は、要素を二項ヒープへ挿入したあと、最小値を繰り返し取り出して昇順にする整列である。
二項ヒープは、次数（階数）の異なる二項木を根リストとして並べた森である。次数 k の二項木 B_k はちょうど 2^k 個の節点を持ち、根の子として B_{k-1}, B_{k-2}, …, B_0 が並ぶ。各木はヒープ条件（親のキーが子以下）を満たし、根リスト上では同じ次数の木は高々 1 本になるよう、マージ時に二進加算と同じ要領で結合する。
- 挿入: 各要素を次数 0 の木としてヒープへ加え、同じ次数の根があればキーの小さい方を親にして結合する。挿入 1 回は
O(log n)、全体でO(n log n)。 - 抽出: 根リストから最小キーの根を外し、その子たちを逆順につないで別ヒープとみなし、残りと合併する。最小を 1 つ得るたびに
O(log n)、n回でO(n log n)。 - 書き戻し: 取り出したキーを配列の先頭から順に書けば昇順になる。
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.000137 | 0.002817 | 8 | 8 |
| 512 | 0.000270 | 0.000577 | 16 | 16 |
| 1024 | 0.000644 | 0.001087 | 32 | 32 |
| 2048 | 0.001387 | 0.002225 | 64 | 64 |
| 4096 | 0.003125 | 0.005242 | 128 | 128 |
| 8192 | 0.006309 | 0.009868 | 256 | 256 |
| 16384 | 0.013944 | 0.027110 | 512 | 512 |
| 32768 | 0.027132 | 0.071452 | 1024 | 1024 |
| 65536 | 0.066323 | 0.117900 | 2048 | 2048 |
| 131072 | 0.146329 | 0.252688 | 4096 | 4096 |
| 262144 | 0.261555 | 1.349849 | 8192 | 8192 |
計測に使用したコードを表示する
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::{
alloc::{GlobalAlloc, Layout, System},
env,
process::Command,
sync::atomic::{AtomicUsize, Ordering},
time::{Duration, Instant},
};
/// Counts live heap bytes and the high-water mark so auxiliary sort buffers
/// (swap Vecs, etc.) are measured as explicit heap growth during the sort.
struct TrackingAllocator;
static LIVE_BYTES: AtomicUsize = AtomicUsize::new(0);
static PEAK_BYTES: AtomicUsize = AtomicUsize::new(0);
fn record_alloc(size: usize) {
let live = LIVE_BYTES.fetch_add(size, Ordering::Relaxed) + size;
PEAK_BYTES.fetch_max(live, Ordering::Relaxed);
}
unsafe impl GlobalAlloc for TrackingAllocator {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
let ptr = System.alloc(layout);
if !ptr.is_null() {
record_alloc(layout.size());
}
ptr
}
unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
LIVE_BYTES.fetch_sub(layout.size(), Ordering::Relaxed);
System.dealloc(ptr, layout);
}
unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
let ptr = System.alloc_zeroed(layout);
if !ptr.is_null() {
record_alloc(layout.size());
}
ptr
}
unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
let new_ptr = System.realloc(ptr, layout, new_size);
if !new_ptr.is_null() {
LIVE_BYTES.fetch_sub(layout.size(), Ordering::Relaxed);
record_alloc(new_size);
}
new_ptr
}
}
#[global_allocator]
static GLOBAL: TrackingAllocator = TrackingAllocator;
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],
);
// Seed 0 is a fixed point of the xorshift below, so it would degenerate into
// yet another all-equal case instead of a 4-value mix. Start at 1.
for seed in 1..=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 micros(d: Duration) -> u128 {
d.as_micros()
}
fn input_array(size: usize, seed: u64) -> Vec<usize> {
shuffled(size, seed)
}
/// Peak heap growth during `benchmark_sort`, in KiB (explicit buffers such as swap).
fn run_once(size: usize, seed: usize) -> (u128, usize) {
let mut array = input_array(size, seed as u64);
let base_bytes = LIVE_BYTES.load(Ordering::Relaxed);
PEAK_BYTES.store(base_bytes, Ordering::Relaxed);
let start = Instant::now();
benchmark_sort(&mut array);
let elapsed = start.elapsed();
let peak_bytes = PEAK_BYTES.load(Ordering::Relaxed);
let aux_kb = peak_bytes.saturating_sub(base_bytes) / 1024;
let expected: Vec<usize> = (1..=size).collect();
if array != expected {
panic!(
"sort failed with seed {} for size {}",
seed,
size
);
}
(micros(elapsed), aux_kb)
}
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 == "--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 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 aux_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;
}
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