バイナリヒープの使い方

プログラマーに欠かせない、配列の処理を最適化する方法

こんにちは。開発担当のマットです。
プログラムし始めたときのことを振り返ってみました。

バイナリヒープとの出会い・・・

何か面白いアプリケーションを作ろうと思って、プログラミングを勉強している方が多くいると思います。
特にゲームを作ろうと思っている方…

私もプログラミングの勉強を始めたころ、いずれゲーム作成に挑戦しようかと思っていました。
最初に作ったプログラムはJavascriptの”Hello World”でしたが、その後とても簡単なシミュレーション・ゲームを作ることに挑戦しました。

ランダムに生成された世界地図上で、多くの国や部族が戦いあって敵を全て倒すと勝つというごく一般的なゲームでしたが、作ることはとても楽しかったです。

世界地図のランダム生成アルゴリズムが完成し、次は敵の国を作ることに挑戦しました。
敵国の動きがあまりにも読みやすかったら困るので、AIのコーディングに結構時間をかけてしまいました。

ある程度できあがって、実行しようと思ったら、、、
ガタガタと重くなりました。
処理が重くて、敵の駒が動くのに数秒かかるようになってしまいました。

まだJavascriptの世界から卒業していなかったため、重くなっていることをブラウザのせいにし「ブラウザに頼らない言語で書いていたら問題はなかった」と信じて一旦ゲームを忘れました。

その後ある日、Javaでゲームを開発しているYoutubeシリーズを見て前に作ったゲームを思い出し、再びゲーム作成に挑戦しようと決めました〜でも今回はJavaで！

今回は全く違うゲームですが、AIを同様に作ってみました。

「今回は速い！」
「今回は問題無い！」
と思いきや、またガタガタ重くなってしまいました。。。

ブラウザのせいにしていたのは大間違いで問題は私が書いたコードにありました。

コードを必死に読んで、デバッギングをして、問題を特定できました！
一つのものすごい重いファンクションのせいでした。

そのファンクションはある配列の中の一番少ない値を返してくれるものでした。
なお、そのファンクションは一秒間に何度も呼び出される。

つまり、もし配列に1000個の値が入っているとしてその処理を一秒間に1000回読んでしまえば、毎秒毎秒100万の比較処理となってしまいます。

恐ろしいループの中のループでした。

配列の最小値、(または最大値)を取得する軽い方法はないか？と悩んで、調べたらバイナリヒープに出会いました。

バイナリヒープとは？

バイナリヒープは「二分ヒープ」とも呼ばれますが、簡単に説明するとバイナリヒープは、
必ず、最小値（または最大値）が常に最初のキーに入るよう管理をきちんとされている配列です。

つまり、配列がarrayとしたら、arrayの最小値（または最大値）は必ずarray[0]にあります。
これがあると、ループをしなくても最小値・最大値をすぐ取得することができ負荷を減少するものとなります。

でも、まさか配列をソートすることになってしまうと余計処理時間がかかりそうので具体的にどうやってするのでしょうか？

配列に潜んでいる特徴

通常、配列をこのように想像します。
0から数えるキーがありそれぞれのキーに値が当てはまります。

しかし、形を変えて想像すると配列に潜んでいた面白い特徴を見ることができます。
それぞれのキーに親子関係を作ることができるのです。

このように並ぶと、
array[0] の子供は array[1]とarray[2]
array[3] の子供は array[7]とarray[8]
array[5] の親は array[2]
array[4] の親は array[1]
などなど・・・

パターンは既に見られているかもしれませんが、
親から見た場合、
親 = n としたら
左の子供 = n*2+1
右の子供 = n*2+2

子供から見た場合、
子供 = n としたら
親 = (n-1)/2 *分数を捨てる

バイナリヒープでできること

このバイナリヒープに値を入れる時、
または、バイナリヒープから値を削除する時、
その値の親と子供の上下関係さえ守れば、最小値・最大値は必ず、array[0]になります。

詳しく、説明します。
*説明では、「最小値」を返すバイナリヒープを紹介しますが、最大値を返すヒープは同様な動きです。

バイナリヒープにINSERT

バイナリヒープに新しい値を挿入する時、その値を配列の一番後ろに付け加えます。
次、新しく入れた値をその親と比較します。
もし新しい値の方が大きい場合、何もしません。
けれども新しい値の方が小さい場合、親と場所を交換し動作を繰り返します。

これをきちんとすると、最小値が必ず、「ルート」(array[0])の位置に上がってきます。

先ほどの配列に「3」を挿入してみましょう。

バイナリヒープからPOP

最小値を配列から取って削除したい場合、動作が反対となります。
まずは最小値（array[0]にあるもの）を消し、配列の一番最後の値をarray[0]に持ってくる。
その新しくなったarray[0]を子供達と比較し、大きければ一番小さい子供と場所を交換し動作を繰り返します。

バイナリヒープの特長

通常1000個の値を持っている配列の最小値を取得しようと思ったら、1000回ループしなければなりません。

でもデータをバイナリヒープの形で管理したら、最小値をループせずに取得でき最大でも9回の比較だけでヒープを整え直すことができます。
(1,000 <　2^10)

配列が大きければ大きほど最適化の効果が見られます。
例えば、1,000,000個の値を持っている配列でも最大でも、たったの19回の比較で整え直すことができます。1,000,000回ループするより速いでしょう。
(1,000,000 <　2^20)

実際のコード

私は最近Sportareの開発に関わり、Swift言語でのプログラミングが好きになりました。

そこでSwiftで書いたバイナリヒープのコードを紹介したいと思います。

通常ならばもっとコード整理しますが、以下のコードはバイナリヒープを把握するために作ったのでそのままベタ書きしました。
Swiftに慣れていない方でも、すぐわかると思います〜

これからも、頑張りましょう！