問１ 問２ 問３ 問４ 問５ 問６ 解答例（若林研二氏）
問 5
優先順位付き待ち行列のプログラムの実現に関する次の記述を読んで，設問
1〜4
に答えよ。
待ち行列は，最初に入ったデータが最初に取り出されるデータ構造である。優先
順位付き待ち行列は，到着時刻よりも優先順位を重視する待ち行列である。優先順
位付き待ち行列では，優先順位が高いものは到着時刻が後でも優先順位の低いもの
より先に取り出される。優先順位が同じものは到着時刻順に取り出される。
優先順位付き待ち行列のライブラリプログラムを書くことになった。作成するラ
イブラリの外部インタフェースは次の二つである。
(1) put(priority, id)
識別番号 id を優先順位の値 priority で待ち行列に入れる関数
(2) get()
待ち行列の先頭の識別番号を取り出す関数
使用するプログラム言語では，動的なメモリ管理ができないので，待ち行列のデ
ータ構造には配列を使う。配列の一つの要素には，優先順位，到着時のタイムスタ
ンプ，識別番号の情報を入れる。以下では，説明を簡単にするために，配列を
Q で
表し，配列の i 番目の要素の優先順位を Q[i].pri，タイムスタンプを
Q[i].time，
識別番号を Q[i].id と表すことにする。配列の添字は 1 から始まるものとする。待
ち行列に現在格納されているエントリ数を n で表す。同じタイムスタンプをもつエ
ントリはないものとする。
ここでは，優先順位は数値の小さい方が優先される。優先順位が同じ場合は，タ
イムスタンプの小さい方が優先される。これによってすべてのエントリを，完全に
順序付けることができる。以後，“優先度が高い”と表記した場合は，上のように完
全順序を付けて並べ換えたときに前にくることを意味する。また，待ち行列の最大
エントリ数 N は分かっているものとする。
プログラムを作成するに当たり，次の二つの方法を考えた。
[方法 A〕
データを入れるときは配列の最後に追加し，取り出すときには，優先度の一番
高いものを検索して取り出す。配列の途中から抜き出したときには，抜き出した
場所に，配列の一番最後にあるデータを移す。get と put の処理は次のとおりで
ある。
put:
n ← n + 1
Q[n] にデータを入れる
get:
Q[i] (i = 1，2，...，n )の中で，優先度が一番高い Q[k] を探す
id ← Q[k].id
Q[n] のデータを Q[k] に移す
n ← n - 1
return id
〔方法B〕
データ表現としてヒープを採用する。ヒープは半順序木を配列上に表現したも
ので，木の根を配列の Q[1] に置く。ヒープでは，Q[i] の左の子供は
Q[2*i] に，
右の子供は Q[2*i+1] に置く。2*i あるいは 2*i+1 が n より大きいときは，
Q[i] の子供は存在しない，あるいは右の子供は存在しないとみなす。したがって，
ヒープで表現できる木は完全 2 分木か，完全 2 分木の葉を右の方から幾つか取り
除いた形の木だけである。
ヒープではすべてのノードにおいて，親の優先度は左右のどちらの子供よりも
高いので，根の優先度が最高となる。半順序木の例を図に示す。図のノード中の
数値は優先順位を表す。この例では同じ優先順位のものは存在しないので，タイ
ムスタンプと識別番号は省略した。
ヒープを使ったときの，put と get の処理は次のとおりである。
put:
n ← n + 1
Q[n] にデータを入れる
r ← n
r が 1 になるか，Q[r] の親の優先度が Q[r] の優先度より高くなるまで次を繰
り返す
Q[r] の親と Q[r] のデータを交換する
r ← Q[r] の親の添字
get:
Q[1] のデータを取り出す
Q[n] のデータを Q[1] に移動する
n ← n - 1
r ← 1
Q[r] に，Q[r] より優先度の高い子供が存在する間，次を繰り返す
優先度の高い方の子供と Q[r] のデータを交換する
r ←交換した子供の添字
設問 1
図の半順序木をヒープで表現したときの配列の各要素の優先順位を示せ。こ
のデータに対し，get()を 1 回行った後，put(6，id)を行った。それぞれの
操作後の配列の状態を同様に示せ。
設問 2
Q[i] のエントリの方が Q[j] のエントリより優先度が高いことを表す論理式
を示せ。タイムスタンプを比較するときは，時間的に前のものが小さいとする。
論理演算には not，and，or を，比較演算には，= ，< ，>を使え。比較演算子
は論理演算子より先に評価されるものとする。比較演算子間の評価の優先順位
はすべて同じとし，論理演算子は，not，and，or の順に評価される。
設問 3
方法 B において，get，put の処理の中で必要な次の内容を r を使って示せ。
ただし，整数の除算は切捨てを行うものとする。
(1) Q[r] の親の添字
(2) Q[r] を親としたときの左右の子供の添字
(3) Q[r] に子供が存在しないという条件
(4) Q[r] に右の子供が存在しないという条件
設問 4
待ち行列にデータが 100 個，1,000 個，2,000 個あるときに，put()と
qet()
を交互に 100,000 回行って処理時間を計測した。方法 A，方法 B の処理時間を表
しているのは，どれか。それぞれ計測結果 1〜3 の番号で答えよ。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
------------------------------------------------------------------------