sodefrin.worksodefrin.work2019-10-26ヒープソートとプライオリティキューアルゴリズムの勉強足りていないなと思いまして、アルゴリズムイントロダクションを読んでいます。アウトプットしておくと覚えがいいとのことなので、まとめていきます。今回はヒープソートとプライオリティキューについて。sortとcontainer/heapの実装についても触れます。分木の中で、親要素と子要素の間に大小関係が存在するものをヒープといいます。つの子ノードを持つような木構造です。ような配列として表現することもできます。ヒープヒープでは親要素と子要素の間に大小関係が存在します。ヒープに並び替えたものです。4ヒープソートの仕組みヒープソートは以下のような手順で実行されます。ヒープを作り直すという手順を繰り返すことで、ソートを実現します。ついて軽くまとめます。ヒープを再構築する方法です。ヒープを再構築していきます。図が多くなるので省略します。ヒープになっています。葉ノードから親ノードへ向けて順に実行していくことで実現されます。packageでは、ソートアルゴリズムとしてクイックソートとヒープソートと挿入ソートが内部的に利用されています。)要素数が少ない場合には単純な挿入ソートを、要素数が多い場合は平均的な性能に優れるクイックソートをまず試し、一定の試行回数でソートが完了しなかった場合にヒープソートに切り替わります。あることが理由であると思われます。ヒープソート本体の実装は以下の通りです。手続きに対応していることがわかります。プライオリティキューの仕組みプライオリティキューもヒープを利用して実現されます。プリラオリティキューは、キューなので値の追加(PUSH)と取得(POP)の2つの操作を定義する必要があります。