sirocco https://blog.hatena.ne.jp/sirocco/ sirocco の書いてもすぐに忘れるメモ https://sirocco.hatenadiary.org/ Ruby Algorithm 常に子よりも親が大きい（小さい）値の二分木をヒープという。2分木を配列で表現すると各要素の位置関係は n の親は n - 1 / 2 n の左の子は 2 * n + 1 n の右の子は 2 * (n + 1) となる。 0 | +--+--+ 1 2 | | +-+-+ +-+-+ | | | | 3 4 5 6 [0,1,2,3,4,5,6] S式で表現すると以下になる。 (0 ;; 0 には 1 と 2 の子がある。 (1 (3 * *) (4 * *)) (2 (5 * *) (6 * *)))ヒープの条件を満たしながらデータを追加していく。 def parent(n); (n - 1)… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsirocco.hatenadiary.org%2Fentry%2F20100103%2F1262474543" title="常に子よりも親が大きい（小さい）値の二分木をヒープという。 - sirocco の書いてもすぐに忘れるメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2010-01-03 08:22:23 rich https://sirocco.hatenadiary.org/entry/20100103/1262474543 1.0 100%