データ構造　第05講「大きい順にデータを出したい」１ - 武蔵高中　ＣＰＵ愛好会　活動日誌

前回までは

要素数の分からない（あるいは処理が長引くにつれて増えていく）データを格納するための方法について学んできました。
今回からは実際に使う時に便利なデータ構造について学んでいきます。

例題

まずは例題を投下します。すぐに解説してしまうので、少し自分で考えたいという方は問題より下を見ない様に気をつけてください。
http://poj.org/problem?id=3253より

【上記URLの問題の、『プログラミングコンテスト　チャレンジブック』（参考文献）による訳を引用】
　農夫ジョンは、フェンスを修理するため、とても長い板からn個の板を切り出そうとしています。
切り出そうとしている板の長さはL1,L2,……,Lnであり、元の板の長さはちょうどこれの合計になっています。
板を切断する際には、その板の長さの分だけのコストがかかります。
　例えば、長さ21の板から長さ5,8,8の3つの板を切り出したいとします。
長さ21の板を長さ13と8の板に切断すると、コストが21かかります。
その13の板を5と8の板に切断すると、コストが13かかります。
合計で34のコストがかかります。
　最小で、どれだけのコストですべての板を切り出すことができるでしょうか。
	制約
	1≦n≦20,000
	1≦Li≦50,000

（補足：Liとは、L1,L2,……,Lnの中の任意の１つ、という意味）

例題の解説

この時、切り出す回数は、何があろうとn-1回です。これは変わりません。同じ回数切るなら、一回一回のコストを安く収めたいですね。
ここで、問題を「L1,L2,……,Lnの板を接続して1枚にする」と読み替えましょう。また、接続するn-1回の内、LiやLiが含まれている板を使う回数を「Liの使用回数」と言うことにします。合計コストは「Liの長さ×Liの使用回数」の和で求められます。
すると、コストをできるだけ小さくしたいので、短いものほど使用回数を増やしたく長いものほど使用回数を減らしたい事が分かります。
そのためには、「各回で短い方から2枚選んでそれら接続していく」という方法が取れます。この事は、「初回に一番短い板と二番目に短い板をを使わない場合はコストが最小にならないという組み合わせがある」事から背理法（そうでない場合は不都合が発生する）により証明できます。
例えば{1,2,4,8,16,32}というLの組み合わせがあったとします。“短い方から選んでいく法”では、{1,2,4,8,16,32}→{3,4,8,16,32}→{7,8,16,32}→{15,16,32}→{31,32}→{63}となり、すべての回で「1」および「1を含むもの」、「2」および「2を含むもの」が使われています。それ以外の方法ではせっかくの短い「1」「2」の使用回数が減ってしまいますね。

という訳で、小さい方から取り出したい訳なんだ

そういう時に、「プライオリティキュー（優先度キュー）」というデータ構造が大変便利です。これは何かと言うと、「入れる順番に関わらず、取り出す時は常に最大/最小（設定によって比較の方法は異なる）の要素を取り出す」ものです。
※以下、数値の大小の代わりに「優先度の高い低い」という表現を使います。
ちなみに、単に「キュー」と言う場合は「一番先に入れた要素を取り出す」、またキューの対義語の「スタック」は「一番最後に入れた要素を取り出す」というものを指します。
しかし、ただ何も考えずにlistやvectorといった直線的な配列にデータを入れただけでは、入れるあるいは取り出す度に配列を優先度順にソート（並び替え）しなければなりません、これでは動作が重くなってしまいますよね。
ここで、優先度キューの実装によく使われるのが、「ヒープ」というデータ構造です。要するに、「データを入れた時点で最高優先度のものが一目で分かる状態にできて、しかもデータを取り出した次にも（次の次にも）最高優先度のものが割と高速に決定できる」という２つの機能を備えたものです。
↓の図の様になっています。（今回の例題では短い板を先に使いたいので、数値の低いものを“優先度の高いもの”と設定した）

ヒープでは、辺によって繋げられた上下の関係だけが意味をなします。
辺の上側に優先度の高い（今回：数値の小さい）ものが、下側に低い（今回：数値の大きい）ものが入れられています。
こういう、一番上の一個の丸を開始点（この“根”という）として、そこから下へ下へと伸びていく構造を「木」と言います。ヒープは、この内「二分木」という、「一個の丸（ノード）につき、それに繋がる下位のノード（子）は２つまでである」ものの一例です。
要素を追加する時は、まず空いてる場所にその要素を追加します。

追加した要素の方が、その親より優先度が高くなってしまっていますね。それではここを入れ替えて、親の方が優先度が高くなる様に直しましょう。
ちなみに、逆側の子（[11]25）については、元々子より優先度の高かった親（[5]22）が入れ替えによって、更に高く（10）なるので、考える必要はありません。

これでも、まだ追加した要素（[5]10）と次の親（[2]18）でも優先度関係が逆ですね、入れ替えましょう。

これで追加はできました。次は要素の取り出しを行いましょう。
「常に子より親が優先度が高い」の法則により、根が一番優先度の高い要素である事が明らかです。
まず、根の中身を消去して、仮に一番最後の（一番下の子である）要素を根の所に移しましょう。

まあ、もちろん仮の根（[0]22）が一番優先度の高いはずがありませんよね。
では、その２つの子（[1]3,[2]10）のうち、どちらかが現在一番優先度の高いものです。だから、２つの子を比べて、より優先度の高い方と仮の根を入れ替えます。

同様にして、「どちらの子よりも優先度が高い」か、「子が存在しない（一番下の子である）」という状況になるまで、入れ替えていきましょう。

ヒープの実装について

前回説明したlistの様に、ポインタを使って実装することもできます。
また、先程の図に書いた「[i]」の様に、常に子の要素番号を、「親の要素番号*2+1」と「親の要素番号*2+2」に割り当てるようにする事で、vectorでも実装できる様になります。
（図）

今回のまとめ

ヒープによる優先度キューの実装の仕組みを解説しました。次回は実際にＣ＋＋にデフォルトで実装されているpriority_queueの使い方と、今回挙げた例題の解答プログラムを書きます。

用語集

※今回、出てくる用語が多かったので並べました。
・プライオリティキュー（優先度キュー）……取り出す時は常に優先度の高い要素を取り出す。
・木……一番上位である「根」から下位へ下位へと伸びる構造。
・二分木……木の一種。一つの親につき子は２つまで。
・ヒープ……二分木の一種。親は必ず子より優先度が高い。優先度キューの実装に用いられる。
・ノード……木の要素
・根……一番上位にあるノード
・辺……ノード同士を結ぶ
・親子……辺で結ばれた上位のノードと下位のノード

参考文献

【書籍】
秋葉拓哉、岩田陽一、北川宜稔『プログラミングコンテスト　チャレンジブック』（毎日コミュニケーションズ、2010年09月）
【ネット】
ソースコード探険隊「ヒープ [Heap]」http://www.codereading.com/algo_and_ds/ds/heap.html
Programming Place Plus「●C++編（標準ライブラリ）　第７章　priority_queue」http://www.geocities.jp/ky_webid/cpp/library/007.html
未確認飛行 C「priority_queue（C++STL）」http://ufcpp.net/study/stl/priority_queue.html