Zenn
Open9

Rustの優先度付きキューについて(std::collections::BinaryHeap)

Rust
algorithm
優先度付きキュー
ahoxa1rxahoxa1rx
pub struct BinaryHeap<T, A = Global>
where
    A: Allocator,
{  /*private fields */ }

BinaryHeap構造体

ahoxa1rxahoxa1rx

Binary Heapについて

2分木構造のヒープ
2分木に以下の2つの制約を追加する。

  • すべてのノードは子ノードよりも大きい値を持つこと (heap property)
  • 完全2分木になること (shape property)
    • 要素数が完全2分木を満たすことができない場合、ノードは左から右に順に埋める
    • 兄弟ノード間は自由に入れ替え可能
ahoxa1rxahoxa1rx

BinaryHeap概要訳

2分木ヒープで実装された優先度付きキュー。
基本はmax-heap(より大きい値が親になる)。
要素がヒープにある場合、Ordtraitによって決定されるような順序変更による値の変更は論理エラーになる。
通常こうしたエラーは内部可変性、大域状態、I/O、unsafeなコードによって起こりうる。
予期しない論理エラー(原文:such a logic error is not specified)の結果はBiniaryHeapによってカプセル化され、未定義動作にはならない。これはパニックや不正な結果、拒否、メモリーリーク、実行が終わらない状態を含む。
BinaryHeapが提供するAPIの動作は、内部要素の相対的順序が変更されない限り、ドキュメントに記述された動作を保証する。(後略)

ahoxa1rxahoxa1rx

2分木ヒープの挙動について
max-heapの場合、最大値は先頭要素をとればいいだけなので O(1)。
値の追加の場合、末端ノードに子として追加され、値が親より大きければSwapを繰り返すので、最悪Swap回数は階層分になる。例えばヒープのサイズが追加後17の場合、階層は5階層になるので最悪5回。BinaryHeapは2分木なので、この階層はlog_2 nになる。よって計算量はO(1) \to O(\log_2 n)。

ahoxa1rxahoxa1rx

BinaryHeapの挿入時の様子

use rand::Rng; // 0.8.5
fn main() {
    use std::collections::BinaryHeap;
    
    let mut heap = BinaryHeap::new();
    let mut rng = rand::thread_rng();
    
    for _i in 1..10 {
        let x: i32 = rng.gen::<i32>() % 30;
        heap.push(x);
        println!("{:?}", heap);
    }
}

   Compiling playground v0.0.1 (/playground)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.54s
     Running `target/debug/playground`

Standard Output

[-10]
[-4, -10]
[-4, -10, -9]
[11, -4, -9, -10]
[15, 11, -9, -10, -4]
[15, 11, -1, -10, -4, -9]
[15, 11, 9, -10, -4, -9, -1]
[29, 15, 9, 11, -4, -9, -1, -10]
[29, 15, 9, 11, -4, -9, -1, -10, -28]

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=3d074474356129513d3425df455b4a7e

ahoxa1rxahoxa1rx

配列の順序は2分木を幅優先で行きがけ探索したものになる。同階層の順序に意味は無いことがわかる。

ahoxa1rxahoxa1rx

Ordトレイトについて

std::cmp::Ord

BinaryHeapは追加時などにノード間で比較を行う必要があるため、必ず比較演算ができる型しか要素にもつことができない、Ordはその制約のためにTに課せられるTraitである。

問題のノード単位となる構造体に対してなにか比較を与えられるような計算を考え、fn cmp()として実装をすればよい。

pub trait Ord: Eq + PartialOrd {
    // Required method
    fn cmp(&self, other: &Self) -> Ordering;
}

これはドキュメントに実装例が乗っているので参考にされたし。

ahoxa1rxahoxa1rx

すでに存在しているA*アルゴリズムの最短経路問題に適用してみた

https://github.com/raiga0310/maze-solver-with-a-star-algorithm/commit/6a225435dd54bb693ad83f2a1d0d56c53c024f7b

  • path-findingはだいたいmin-heapなのでReverse(比較演算の結果を逆にして計算してくれる)をつかってmin-heapを実現する
  • expand,generateがまとまって簡単になった
  • ただまぁ、おそらく既存の実装がよろしくないので結構煩雑な感じになってしまった