二分ヒープ：配列でつくる優先度付きキュー

大きい順・一つずつ挿入を押してみましょう。新しいキーはヒープ内のどのキーよりも小さいため、底から根まで上がります。1段につき比較と交換が各1回。根は0回、次の2個は各1回、その次の4個は各2回、最後の8個は各3回で、合計34回です。続いて大きい順・最後の親から調整を押します。同じ15個を到着順に並べ、子を持つ位置を6から0へ順に下方修正します。キーが下がれるのは、その下に段があるところまで。15個の位置のうち8個は葉で、下には何もありません。逐次挿入ではそれぞれ3段分の手間がかかった位置が、こちらでは何の操作も要らないのです。高さの合計は11で、1段につき比較は2回なので、計22回。どのヒープでも、高さの合計は n から「n を二進法で表したときの 1 の個数」を引いた値になります。そのため、この構築方法の比較回数は常に 2n 回未満です。1,023個のキーが大きい順に届く場合、両者の比較回数は8,194回と2,026回になります。

小さい順・一つずつ挿入を押してみましょう。新しいキーは初めから親以上なので、比較は1回、交換はなく、計14回です。最後の親から調整に切り替えても14回。各親で子どうしを比較し、小さいほうの子と親を比較すると、そこで止まるからです。根以外のキーは少なくとも1回は比較する必要があるため、14回はどちらの方法でも下限です。ここから比較回数が増えるにつれ、両者に差がつきます。大きい順の入力では、逐次挿入は上限に達します。シャッフルした入力なら、比較回数は下限にずっと近くなります。1,000個のキーを200回シャッフルした実験では、平均比較回数は逐次挿入が2,235回、最後の親からの構築が1,862回でした。同じキーを大きい順に逐次挿入した場合の7,987回より、かなり少なくなっています。15個では差はわずかです。シャッフルを何度か押すと、逐次挿入のほうが少ない回数で済むこともあります。

ヒープの条件は、どのキーもその子以下であることです。異なる7個のキーの並べ方5,040通りのうち、この条件を満たすのは80通り。根には最小値が入り、残る6個のうちどの3個を左部分木に割り当ててもかまいません。ただし、左右の部分木もそれぞれヒープである必要があります。この個数は、7! を各部分木の大きさの積 7 · 3 · 3 で割ると求まります。15個の場合、結果の表にあるとおり、並べ方1,307,674,368,000通りのうちヒープは21,964,800通り。その中で昇順に並んでいるのはわずか1通りです。許される並べ方が多いからこそ、ヒープは少ない手間でつくれます。小さい順にそろうのは、キーを取り出していくときです。ヒープソートを押してみましょう。根を取り出すたびに末尾のキーで空きを埋め、下方修正すると、次の最小値が根に現れます。12個のキーが3, 7, 12から93まで、順に出てきます。