科目Bのヒープ問題の解き方｜親子の入れ替えを図で追う

ヒープって、配列なの？木なの？どっちで考えればいいのか分からない。

科目Bで、添字を2倍したり2で割ったりするコードを見て、何をしているのか分からなくなったことはありませんか？

二分木の問題なら図を描いて追えるのに、ヒープになると配列と木が混ざって見えて、急に難しく感じる。そんな人は少なくないのではないでしょうか。

大丈夫です。ヒープの問題で必要なのは、配列を木の形に描き直すことと、親と子を入れ替えるたびに図を1枚ずつ更新していく手順だけです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、締め切りが近い順にジョブを処理する仕組みのように、いちばん優先度の高いものを素早く取り出したい場面があり、その裏側ではヒープの考え方が使われています。

自分で一から書く機会は多くありません。それでも、仕組みを知っていると、処理が遅いときにどこを疑えばいいのかの見当がつきます。

この記事では、ヒープの問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中で、こうしたアルゴリズムの問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

ヒープの問題は何を聞いているのか¶

最初に、ヒープとは何かを短く押さえておきましょう。何を守るためのデータ構造なのかが分かると、コードの意図が読みやすくなります。

ヒープとは、親の値が子の値以上になるように並べた二分木のことです。この決まりを守っていると、いちばん大きい値が必ず根に来ます。

親の値が子の値以下になるように並べる、逆向きのヒープもあります。どちらの向きなのかは、問題文の説明か、比較の条件を見れば分かります。

試験で問われるのは、値を追加したり取り出したりしたあと、配列の中身がどう並んでいるかです。つまり、入れ替えを何回行い、最後にどの位置に何が来るかを正しく追えるかが問われます。

配列を木として読む¶

ヒープは木ですが、コードの中では配列として扱われることがほとんどです。添字の計算で、親と子の位置関係を表しています。

配列の添字を1から数える場合の関係を、表にまとめました。

たとえば配列 {9, 7, 5, 3, 6} なら、根は添字1の 9 です。その子は添字2の 7 と添字3の 5、さらに 7 の子は添字4の 3 と添字5の 6 になります。

ヒープと二分探索木の違い¶

ここでよく混同されるのが、二分探索木との違いです。二分探索木では、左の子が親より小さく、右の子が親より大きいという左右の決まりがあります。

ヒープには、左右の決まりはありません。決まっているのは、親と子の大小だけです。

そのため、ヒープの左右どちらの子が大きいかは、そのときどきで変わります。木のたどり方そのものに不安がある場合は、こちらの記事で先に確認しておくと安心です。

【関連記事】科目Bの二分木問題の解き方｜節点をたどる順番を解説

まず目を付ける場所¶

ヒープとは何かがつかめたら、次はコードのどこから読むかを決めます。ヒープの問題では、目を付ける場所が3つあります。

ひとつ目は添字の計算、ふたつ目は比較の向き、みっつ目はループが止まる条件です。この順番で見ていくと、コードの役割がはっきりします。

添字の計算で上に向かうか下に向かうかを見る¶

最初に見るのは、添字を2で割っているか、2倍しているかです。2で割っていれば親へ、つまり下から上へ向かっています。

2倍していれば子へ、つまり上から下へ向かっています。値を追加するときは下から上へ、根を取り出すときは上から下へ動くのが基本です。

この一点を見るだけで、そのコードが追加の処理なのか、取り出しの処理なのかの見当がつきます。

比較の向きと止まる条件を見る¶

次に見るのは、親と子を比べている条件です。子のほうが大きいときに入れ替えていれば、根に最大値が来るヒープです。

最後に、ループがどこで止まるかを確かめます。根にたどり着いたときか、入れ替える必要がなくなったときに止まるのが普通です。

例題：値を追加して上へ移動させる¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のコードは、親の値が子の値以上になるヒープに、新しい値 v を追加する手続です。配列の添字は1から始まるものとします。

○push(整数型の配列: heap, 整数型: v)
  整数型: i, p, tmp
  heap の末尾に v の値を追加する
  i ← heap の要素数
  while (i が 1 より大きい)
    p ← i ÷ 2 の商
    if (heap[p] が heap[i] より小さい)
      tmp ← heap[p]
      heap[p] ← heap[i]
      heap[i] ← tmp
      i ← p
    else
      i ← 1
    endif
  endwhile

まず、新しい値を配列の末尾、つまり木のいちばん下に置きます。そこから親と比べ、親のほうが小さければ入れ替えて、1つ上に上がります。

親のほうが大きくなった時点で、決まりは守られています。else の中の i ← 1 は、ループを終わらせるための代入です。

では、{9, 7, 5, 3, 6} というヒープに 10 を追加すると、配列はどうなるでしょうか？

木の図で入れ替えを描く¶

追加した直後の配列は {9, 7, 5, 3, 6, 10} です。10 は添字6に入るので、親は 6 ÷ 2 の商で添字3の 5 になります。

入れ替えの前後を、木の図で描いてみましょう。

追加直後            1回目の入れ替え後      2回目の入れ替え後
      9                  9                     10
    /   \              /   \                  /   \
   7     5            7     10               7     9
  / \   /            / \   /                / \   /
 3   6 10           3   6 5                3   6 5

10 が 5 と入れ替わって1段上がり、さらに根の 9 と入れ替わって、いちばん上まで上がりました。最後の配列は {10, 7, 9, 3, 6, 5} です。

トレース表で添字と値を追う¶

図だけでは、どの添字を比べたのかが分かりにくくなることがあります。そこで、ループ1回ごとの i と p、比べた値をトレース表に書きます。

2回目のあと i は 1 になり、i が 1 より大きいという条件が偽になってループを抜けます。入れ替えは全部で2回でした。

もし追加した値が 8 だったら、1回目で 5 と入れ替わったあと、2回目に根の 9 と比べて止まります。結果は {9, 7, 8, 3, 6, 5} です。

根を取り出すときは下へ移動させる¶

ヒープから最大値を取り出すときは、逆向きの動きになります。根の値を取り出したあと、配列の末尾の値を根に移し、そこから子と比べて下へ移動させます。

先ほどの {10, 7, 9, 3, 6, 5} から 10 を取り出してみましょう。末尾の 5 を根に移すと、配列は {5, 7, 9, 3, 6} になります。

ここで大切なのは、2つの子のうち大きいほうと比べることです。添字2の 7 と添字3の 9 のうち大きいのは 9 なので、5 と 9 を入れ替えて {9, 7, 5, 3, 6} になります。

5 は添字3に移りました。その子の添字6と7は要素数の 5 を超えているので、ここで止まります。

トレース表を書く作業そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

間違いやすい選択肢の見分け方¶

ヒープの問題では、添字や比較の向きを少しだけ変えた選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

よくある誤りを表にまとめました。

この中でも、特によく狙われるのが添字の式と、取り出しのときに比べる子の選び方です。順番に見ていきましょう。

添字は1始まりか0始まりかを先に確かめる¶

親の添字を求める式は、配列の添字が1から始まるか、0から始まるかで変わります。1始まりなら i ÷ 2 の商、0始まりなら (i − 1) ÷ 2 の商です。

科目Bの擬似言語では、配列の添字は1から始まるのが基本です。ただし、問題文で0から始まると断っている場合もあるので、最初に必ず確かめてください。

迷ったときは、根の子に当たる添字を式に入れてみるのが近道です。1始まりで添字2と3を入れると、どちらも1になります。正しく根を指していれば、その式で合っています。

大きいほうの子と比べる理由¶

取り出しのときに小さいほうの子と入れ替えると、どうなるでしょうか。先ほどの {5, 7, 9, 3, 6} で 5 と 7 を入れ替えると、根が 7 になり、その右の子に 9 が残ります。

親の 7 が子の 9 より小さいので、ヒープの決まりが崩れてしまいます。大きいほうの子を上に上げるからこそ、もう一方の子よりも親が大きいという関係が保たれるのです。

選択肢で迷ったら、この記事の例題のような5個か6個の小さな配列を用意して、1回分だけ入れ替えてみてください。決まりが崩れる選択肢は、その1回で見分けられます。

ヒープはヒープソートという整列の方法にも使われます。値を交換しながら並べる考え方そのものは、こちらの記事でも扱っています。

【関連記事】科目Bのソート問題を解くコツ｜交換される値を追ってみよう

箱の中身を追う問題とつなげて考える¶

ヒープの節を、値と左右の子への参照を持つクラスで表す問題もあります。その場合は、配列の添字の代わりに、矢印の付け替えを追うことになります。

考え方は同じで、親と子を比べて入れ替える、という流れは変わりません。クラスで表した構造の追い方は、こちらの記事で解説しています。

【関連記事】科目Bのクラス・オブジェクト問題の解き方｜インスタンスの中身を表で追う

Giji Academy のシミュレーターで動かす¶

紙の図とトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。値が何度も入れ替わる処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、配列や変数の値が変わる様子を目で確かめられます。自分で描いた木の図と見比べながら進めると、どの入れ替えで予想とずれたのかがすぐに分かります。

試すときは、追加する値を変えてみるのがおすすめです。根まで上がる値、途中で止まる値、まったく動かない値を入れてみると、止まる条件の意味がよく分かります。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、配列の値が入れ替わる様子を確かめてみてください。

まとめ¶

科目Bのヒープの問題は、データ構造の理論を深く問うものではありません。配列を木の形に描き直し、親と子を入れ替えるたびに図と表を更新していけば必ず解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、5個か6個の値が入った小さな配列で十分です。値を1つ追加しては図を描き直す練習を何度か繰り返すうちに、添字を2で割るコードを見ただけで、木のどこを上っているのかが思い浮かぶようになります。

配列と木が混ざって見えても、中でやっていることは親と子を比べて入れ替える、の繰り返しです。次にヒープの問題に出会ったら、まずは配列を木の形に描き直すところから始めてみてください。