学習アルゴリズム

第4章. 盛る

この作品はAIを使って翻訳されている。ご意見、ご感想をお待ちしている：[e-mail]

この章では、次のことを学ぶ：

• キューと プライオリティ・キューのデータ型。

• 年に発明されたバイナリーヒープデータ構造で、配列に格納できる。

• 最大バイナリヒープでは、より大きな数値の優先順位を持つエントリは、より小さな数値の優先順位を持つエントリよりも高い優先順位を持つとみなされる。最小バイナリヒープでは、より小さい数値の優先順位のエントリがより高い優先順位を持つ。

• O(log N)でバイナリヒープに(値、優先度)エントリをエンキューする方法。Nはヒープ内のエントリ数である。

• バイナリヒープで最も優先度の高い値をO(1)で発見する方法。

• バイナリヒープから最も優先度の高い値をO(log N)で削除する方法。

単に値のコレクションを格納するのではなく、エントリのコレクションを格納し、各エントリに値とそれに関連する優先度を数値で表すとしたらどうだろうか。 2つのエントリがあれば、優先順位が高い方が他よりも重要である。今回の課題は、新しい（値、優先度）エントリをコレクションに挿入し、最も優先度の高いエントリの値をコレクションから削除して戻せるようにすることだ。

この振る舞いは、enqueue(value, priority) とdequeue() を効率的にサポートするデータ型であるプライオリティ・キューを定義しており、最も優先順位の高い値を削除する。プライオリティ・キューは、前章で説明したシンボル・テーブルとは異なり、最も優先順位の高い値の削除を要求する際に、事前に優先順位を知る必要がないからである。

混雑したナイトクラブが混雑しすぎると、図4-1のように外に人の列ができ る。 クラブに入ろうとする人が増えると、その人は列の最後尾で待たなければならな くなる。列から最初にナイトクラブに入るのは、最も長く待った人である。この振る舞いは、キュー抽象データ型の本質を表している。enqueue(value) の演算子は、value を追加してキューの最後にある最新の値にし、dequeue() はキューに残っている最も古いvalue を削除する。この経験を表現する別の方法は、"First in, first out"（FIFO）である。これは、"First [one] in [line is] first [taken] out [of line]"（最初に[行に]入ったものが、最初に[行から]取り出される）の略語である。

図4-1. ナイトクラブでキューで待つ。

Node 前の章では、リンクリストのデータストアについて説明した。このデータストアを、キュー用のvalue ：

class Node:
  def __init__(self, val):
    self.value = val
    self.next = None

この構造を使用して、リスト4-1のQueue の実装では、リンクリストの末尾に値を追加するenqueue() 操作を行っている。図4-2は、"Joe"、"Jane"、"Jim "を（この順番で）ナイトクラブキューにエンキューした結果を示している。

"Joe "は最初の利用者からキューから外され、2人の利用者からなるキューとなり、"Jane ...