priority queue

[praɪˈɔrəti kjuː] プライオリティ キュー

1. データ構造の一種で、要素が追加された順序ではなく、各要素に割り当てられた優先度に基づいて取り出されるもの。

各要素に優先度という属性が与えられており、最も優先度の高い要素から順に取り出すことができるデータ構造です。オペレーティングシステムでのタスクスケジューリングや、アルゴリズムの実装（例：ダイクストラ法）など、コンピュータサイエンスの様々な分野で利用されます。

We used a priority queue to manage tasks by urgency. (緊急度でタスクを管理するために、優先度キューを使いました。)

• We: 「私たち」という複数の人を指します。
• used: 「使う」「利用する」という動詞の過去形です。
• a priority queue: 「優先度キュー」という、要素を優先度に従って管理するデータ構造を指します。
• to manage tasks: 「タスクを管理するために」という目的を示します。manageは「管理する」、tasksは「タスク」「課題」の複数形です。
• by urgency: 「緊急度によって」「緊急度に基づいて」という意味です。byは「～によって」、urgencyは「緊急度」を意味します。

A priority queue is often implemented using a heap. (優先度キューはしばしばヒープを使って実装されます。)

• A priority queue: 「優先度キュー」という特定の種類のデータ構造を指します。
• is often implemented: 「しばしば実装される」という意味です。oftenは「しばしば」、implementedは「実装される」という受動態です。
• using a heap.: 「ヒープを使って」という意味です。usingは「～を使って」、a heapは「ヒープ」という別のデータ構造を指します。

Elements are dequeued from the priority queue based on their priority. (要素は優先度に基づいて優先度キューから取り出されます。)

• Elements: 「要素」や「データ項目」の複数形です。
• are dequeued: 「キューから取り出される」「デキューされる」という受動態です。dequeuedは「キューから取り出す」という動詞の過去分詞です。
• from the priority queue: 「その優先度キューから」という意味です。fromは「～から」、the priority queueは「その優先度キュー」を指します。
• based on their priority.: 「それらの優先度に基づいて」という意味です。based onは「～に基づいて」、their priorityは「それらの優先度」を指します。

2. アルゴリズムやデータ構造の文脈で、要素の処理順序が単なる追加順ではなく、定められた優先度によって決定される待ち行列のこと。

一般的なキュー（FIFO - First-In, First-Out）とは異なり、要素の順序は挿入順ではなく、各要素に関連付けられた優先度によって決まります。高い優先度を持つ要素は、たとえ後から挿入されたとしても、低い優先度の要素より先に処理されます。

Implementing Dijkstra's algorithm efficiently requires a priority queue. (ダイクストラ法を効率的に実装するには、優先度キューが必要です。)

• Implementing: 「実装すること」という動名詞です。
• Dijkstra's algorithm: 「ダイクストラ法」というグラフ探索アルゴリズムの名前です。
• efficiently: 「効率的に」という副詞です。
• requires: 「必要とする」という動詞の三人称単数現在形です。
• a priority queue.: 「優先度キュー」というデータ構造を指します。

In a priority queue, the highest priority item is always processed first. (優先度キューでは、最も優先度の高い項目が常に最初に処理されます。)

• In a priority queue,: 「優先度キューでは」という意味です。inは「～の中で」という意味の前置詞句です。
• the highest priority item: 「最も優先度の高い項目」を指します。the highest priorityは「最も優先度の高い」、itemは「項目」「要素」を意味します。
• is always processed first.: 「常に最初に処理される」という意味です。alwaysは「常に」、is processedは「処理される」という受動態、firstは「最初に」を意味します。

Adding an element to a priority queue takes logarithmic time. (優先度キューに要素を追加するのにかかる時間は対数時間です。)

• Adding an element: 「要素を追加すること」という動名詞句です。Addingは「追加すること」、an elementは「一つの要素」を指します。
• to a priority queue: 「優先度キューに」という追加先を示します。toは「～に」という前置詞句です。
• takes logarithmic time.: 「対数時間かかる」という意味です。takesは「（時間が）かかる」、logarithmic timeは「対数時間」を意味します。

関連

• queue
• stack
• heap
• data structure
• algorithm
• scheduling