ビームサーチ用の固定長ヒープZennSilVa496🌿ビームサーチ用の固定長ヒープ2024/01/17に公開2024/02/25Rustデータ構造AtCodertechTL;DRコンパイル時に最大サイズが決められる、二分ヒープFixedHeapを実装しました決めた最大サイズより多く挿入すると、値の小さいものを決めたサイズだけ保持しますモチベーションヒューリスティックな競技プログラミングコンテストで、ビームサーチを打ちたい場面は山ほどありますが、いつも評価値上位の状態の管理をstd::collections::BinarhHeapで無理やりなんとかしています。ヒープの大きさがビーム幅を超えるたびに、1つ削除する処理を書くのは面倒。ビーム幅は予め決まっているのでどうにか楽にできない?と思ってどうにかしました。機能・つかいかたOrdトレイトを実装している型と、ヒープの最大サイズをジェネリックに取りますpush()で挿入ができますが、pop()はありませんiter()やIntoIterトレイトが実装されていますpeek()で最大値の参照が取れますTODOソートされた配列を返すinto_sorted_vec()実装シンプルな二分ヒープがベースですが、ヒープが埋まってから挿入するときは、現状の最大値より小さければ、順序木の根を書き換えdown-heapを行うことで挿入を行います。デバックしてないので、バグを見つけたら教えてください。}}GitHubで編集を提案SilVa496初心1バッジを贈って著者を応援しようバッジを受け取った著者にはZennから現金やAmazonギフトカードが還元されます。Proよくある質問LinksX(Twitter)GitHubメディアキットLegal利用規約プライバシーポリシ。