実験・実装 · 基礎から応用へ

ヒープによる優先度付きキューを実装する

小さなジョブ集合をヒープへ追加し、同じ優先度の順序と親子の条件を確かめます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 整列済み配列とは違う条件を調べる
  2. 同じ優先度の比較規則を決める
  3. 追加と取出しを実行する
  4. 入力を変えて空の境界も確かめる
  5. 計算量と用途の限界
  6. 一件ずつ追加する場合とまとめて作る場合
  7. この記事をロゲイアに質問する理解を確かめる

整列済み配列とは違う条件を調べる

この実験ではPythonのheapqを使い、小さい優先度のジョブを先に取り出します。ヒープで必要なのは親が子以下という条件であり、内部配列全体が昇順である必要はありません。優先度2のfirst、1のurgent、2のsecondを順に追加し、取り出す順番と追加後の親子の関係を検査します。実装を丸写しするより、データ構造の契約を小さな入力で確かめることが目的です。標準ライブラリの最小ヒープのAPIだけを使うため、Pythonの新しい最大ヒープ用機能は必要ありません。

同じ優先度の比較規則を決める

ジョブを優先度とラベルだけの組にすると、優先度が同じ場合はラベルの辞書順で比較されます。投入順を保ちたいなら、それは意図した規則ではありません。そこで優先度、単調に増える連番、ラベルの三要素を格納します。連番は同じ優先度の順序を決め、比較できない任意のジョブ本体へ比較が及ぶことも避けられます。優先度を小さくするほど先に実行するという約束も明示し、緊急度が大きいほど先という別の表示規則と取り違えないようにします。

追加と取出しを実行する

下のコードは、各追加の後に全ての親子について条件を確かめます。この検査は説明用なので一回の追加ごとに線形の仕事が増えます。通常のheappushの計算量そのものと、この検査込みのプログラム全体の計算量を同じものとして扱わないでください。最後に三回取り出し、urgent、first、secondの順であることをassertします。内部配列の一回の表示だけに頼らず、外部へ返す順序を確認するのが重要です。失敗した場合は、まず連番の付け方と比較対象を見直します。

Python 3
import heapq
jobs = [(2, "first"), (1, "urgent"), (2, "second")]
heap = []
for sequence, (priority, label) in enumerate(jobs):
    heapq.heappush(heap, (priority, sequence, label))
    assert all(heap[(i-1)//2] <= heap[i] for i in range(1, len(heap)))
result = [heapq.heappop(heap)[2] for _ in range(len(heap))]
assert result == ["urgent", "first", "second"]
print(result)

入力を変えて空の境界も確かめる

全ての優先度を同じにすると、連番により投入順で取り出せます。全てを異なる優先度にすれば、ラベルの綴りに関係なく優先度順になることを確かめられます。空のヒープから取り出す操作は別途処理が必要で、標準APIでは例外になります。ジョブを追加した後で格納済みタプルをそのまま変更するのも安全な更新方法ではありません。優先度変更や取り消しには、古い項目の無効化、新項目の投入など、重複をどう扱うかを決めた追加設計が必要です。

計算量と用途の限界

n件のヒープで追加と最小値の取出しは通常O(log n)、最小値を先頭から見るだけならO(1)です。既存の配列からheapifyで作る処理はO(n)であり、全てを一件ずつ追加する方法とは分けて考えます。特定IDのジョブを検索する操作や、全件を優先度順に列挙する操作が自動的にO(1)になるわけではありません。期限や公平性を持つ実際のジョブ実行器では、同じ優先度の規則に加えて、長時間待つジョブをどう扱うかも必要になります。

一件ずつ追加する場合とまとめて作る場合

追加の確認として、既にそろった三件のタプルをリストに置き、heapifyでヒープへ変える方法も試せます。結果を全て取り出した順番が、先ほどの逐次追加版と一致することを確かめます。内部配列の並びが同じでなくても、ヒープ条件と取出し順が契約を満たせば問題ありません。同値キーを連番で解消している点も両方でそろえます。比較の途中でラベルを別の型へ変更すると、タイブレークの説明が変わり得るため、入力データと比較規則を一組の再現条件として保存します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 9

学習コースから次を選ぶ