優先度付きキューにも使われる二分ヒープ構造をRubyで実装してみる - $shibayu36->blog;アルゴリズム図鑑 絵で見てわかる26のアルゴリズム 作者:石田保輝,宮崎修一翔泳社Amazon アルゴリズム図鑑を眺めていて、二分ヒープ構造は優先度付きキューに使われることを知った。面白いなーと思うと同時に、そういえば二分ヒープ構造の実装をしたことがなく、あまり理解できていないことに気づいた。そこで簡単にRubyで実装をしてみたのでメモ。簡単なテストケースを作ったので多分合ってると思うけど、もしかしたらバグっているかも... 二分ヒープの詳細は二分ヒープ - Wikipediaも参考。 【2023/01/03 14:01追記】要素数が1の時に要素が空にならないバグがあったので修正しました。コメントありがとうございます。https://github.com/shibayu36/algorithms/commit/6c2ce588f7bc7fb890c6a560c7ab062c6f531a9a
