はじめに: 優先度付きキューは「先着順ではなく重要度順」のキュー
キューは、先に入れたデータを先に取り出すデータ構造です。行列のように、先に並んだものから順番に処理するイメージです。
今回扱う優先度付きキューは、少し考え方が違います。入った順番ではなく、優先度が高いものから取り出します。
たとえば、通常の問い合わせは受付順に処理するとしても、障害対応や緊急の通知は先に処理したいことがあります。このように「次に処理すべきもの」を優先度で選びたいとき、優先度付きキューの考え方が役立ちます。
優先度付きキューを効率よく実装する代表的なデータ構造がヒープです。ヒープは木構造の一種ですが、配列でも表せるため、JavaScriptでも実装しながら理解できます。
優先度付きキューは、入った順番ではなく優先度によって次に取り出すデータを決めるキューです。
普通のキューと優先度付きキューの違い
普通のキューは、先入れ先出しです。先に入れたものを先に取り出します。
const queue = [];
queue.push("通常タスクA");
queue.push("通常タスクB");
console.log(queue.shift());この場合、先に入れた "通常タスクA" が先に取り出されます。
一方、優先度付きキューでは、優先度を一緒に保存します。ここでは、数値が小さいほど優先度が高いものとして考えます。
{ name: "通常タスク", priority: 3 }
{ name: "緊急タスク", priority: 1 }この場合、あとから入ったとしても、優先度が高い "緊急タスク" を先に取り出したくなります。
つまり、普通のキューは「いつ入ったか」を重視します。優先度付きキューは「どれが重要か」を重視します。
普通のキューは入った順番で取り出し、優先度付きキューは優先度の高いものから取り出します。
配列で優先度付きキューを作ってみる
まずは分かりやすさを優先して、配列で優先度付きキューを作ってみます。データを追加し、取り出すときに優先度順へ並べ替えます。
class SimplePriorityQueue {
constructor() {
this.items = [];
}
enqueue(value, priority) {
this.items.push({ value, priority });
}
dequeue() {
this.items.sort((a, b) => a.priority - b.priority);
return this.items.shift();
}
}
const tasks = new SimplePriorityQueue();
tasks.enqueue("通常タスク", 3);
tasks.enqueue("緊急タスク", 1);
tasks.enqueue("確認タスク", 2);
console.log(tasks.dequeue());このコードでは、dequeue() のたびに sort() しています。優先度の数値が小さいものほど前に来るため、shift() で優先度が高いタスクを取り出せます。
学習用としては分かりやすい実装です。ただし、取り出すたびに配列全体を並べ替えるため、データが多い場合は効率がよくありません。
優先度付きキューをよく使う場面では、追加や取り出しをもっと効率よく行いたくなります。そこで登場するのがヒープです。
配列を毎回ソートすれば優先度付きキューは作れますが、データが増えると効率が悪くなります。
ヒープとは何か: 親子関係で優先度を保つ木
ヒープは、親子関係を使って優先度を保つデータ構造です。ここでは、最小値を先に取り出す最小ヒープを考えます。
まず、ヒープは「完全に整列された木」ではありません。二分探索木のように、左側が小さく右側が大きい、という形で全体をきれいに並べるわけではありません。
ヒープで大切なのは、親と子の関係です。
最小ヒープでは、親の値が子の値以下になるように並べます。
1
/ \
2 3
/ \
5 4この例では、一番上の値が最小です。つまり、最小ヒープでは根にある値を見れば、最も優先度の高いものが分かります。
ここで注目したいのは、兄弟同士の順番までは厳密に決まっていないことです。たとえば 2 と 3 の左右が入れ替わっても、親が子以下という条件を満たしていれば、最小ヒープとしては成り立ちます。
1
/ \
3 2
/ \
5 4この形でも、根の 1 が最小であり、それぞれの親が子以下になっています。つまりヒープは、「全体が小さい順に並んでいる構造」ではなく、「一番優先度の高い要素をすぐ取り出せるように、親子関係だけを保つ構造」です。
この割り切りが、ヒープの効率につながります。全体を毎回きれいに並べる必要がないため、追加や取り出しのたびに直す範囲を小さくできます。
ヒープは木構造として説明されますが、実装では配列で表すことがよくあります。配列のインデックスを使うと、親子関係を計算できるからです。
i 番目の要素について、左の子は 2 * i + 1、右の子は 2 * i + 2 で求められます。親は Math.floor((i - 1) / 2) で求められます。
たとえば、次の配列を考えます。
[1, 2, 3, 5, 4]これをヒープの木として見ると、次のようになります。
index: 0 1 2 3 4
value: 1 2 3 5 4
1
/ \
2 3
/ \
5 4配列の 0 番目が根です。0 番目の左の子は 2 * 0 + 1 で 1 番目、右の子は 2 * 0 + 2 で 2 番目です。
1 番目の左の子は 2 * 1 + 1 で 3 番目、右の子は 2 * 1 + 2 で 4 番目です。このように、ポインタを持たなくても、インデックスの計算だけで親子関係を表せます。
ヒープは、親子関係を保ちながら最も優先度の高い要素を根に置くデータ構造です。
ヒープは全体を完全に整列するのではなく、親が子より優先されるという条件だけを保つことで効率よく動きます。
JavaScriptで最小ヒープを実装する
ここでは、数値が小さいほど優先度が高い最小ヒープを実装します。
class MinHeap {
constructor() {
this.items = [];
}
push(value) {
this.items.push(value);
this.bubbleUp();
}
pop() {
if (this.items.length === 0) return undefined;
if (this.items.length === 1) return this.items.pop();
const min = this.items[0];
this.items[0] = this.items.pop();
this.bubbleDown();
return min;
}
bubbleUp() {
let index = this.items.length - 1;
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.items[parentIndex] <= this.items[index]) {
break;
}
[this.items[parentIndex], this.items[index]] =
[this.items[index], this.items[parentIndex]];
index = parentIndex;
}
}
bubbleDown() {
let index = 0;
while (true) {
const leftIndex = 2 * index + 1;
const rightIndex = 2 * index + 2;
let smallestIndex = index;
if (
leftIndex < this.items.length &&
this.items[leftIndex] < this.items[smallestIndex]
) {
smallestIndex = leftIndex;
}
if (
rightIndex < this.items.length &&
this.items[rightIndex] < this.items[smallestIndex]
) {
smallestIndex = rightIndex;
}
if (smallestIndex === index) {
break;
}
[this.items[index], this.items[smallestIndex]] =
[this.items[smallestIndex], this.items[index]];
index = smallestIndex;
}
}
}
const heap = new MinHeap();
heap.push(3);
heap.push(1);
heap.push(2);
console.log(heap.pop());
console.log(heap.pop());push() では、いったん配列の末尾に値を追加します。そのあと、親より小さければ入れ替えながら上へ移動します。この処理が bubbleUp() です。
たとえば、すでに次のヒープがあるとします。
2
/ \
4 5ここに 1 を追加すると、まず配列の末尾、つまり木で見ると一番下の空いている場所に入ります。
2
/ \
4 5
/
1しかし、このままだと親の 4 より子の 1 のほうが小さいため、最小ヒープの条件に反します。そこで 1 と 4 を入れ替えます。
2
/ \
1 5
/
4まだ 1 は親の 2 より小さいので、さらに入れ替えます。
1
/ \
2 5
/
4これで、親が子以下という条件を満たしました。このように、追加した値を必要なところまで上へ上げる処理が bubbleUp() です。
pop() では、根にある最小値を取り出します。そのまま根を空にできないので、末尾の値を根へ移し、子と比べながら下へ移動させます。この処理が bubbleDown() です。
たとえば、次のヒープから最小値を取り出すとします。
1
/ \
2 5
/
4最小値は根の 1 です。これを取り出したあと、木の形を保つために末尾の 4 を根へ移します。
4
/ \
2 5しかし、このままだと根の 4 が子の 2 より大きく、最小ヒープの条件に反します。そこで、より小さい子である 2 と入れ替えます。
2
/ \
4 5これで条件が戻りました。このように、根へ移した値を下へ下げて条件を直す処理が bubbleDown() です。
このように、ヒープでは全体を毎回ソートするのではなく、崩れた部分だけを直します。
ヒープでは、追加時は上へ、取り出し時は下へ入れ替えながら、親子関係の条件を保ちます。
bubbleUp() は追加した要素を上へ動かし、bubbleDown() は根に移した要素を下へ動かしてヒープの条件を回復します。
計算量: なぜヒープを使うのか
配列を毎回ソートする方法は分かりやすいですが、データが増えると重くなります。取り出しのたびに全体を並べ替えるためです。
ヒープを使うと、追加と取り出しを O(log n) で行えます。これは、ヒープが木構造として見ると高さ方向にだけ調整すればよいからです。
要素数が増えても、木の高さはゆっくり増えます。たとえば、要素数が2倍になっても、高さはおおよそ1段増えるだけです。
優先度付きキューでは、「追加する」「最も優先度が高いものを取り出す」という操作を何度も行うことがあります。そのため、毎回全体を並べ替えるより、ヒープで必要な部分だけ直すほうが効率的です。
ヒープを使うと、優先度付きキューの追加と取り出しを O(log n) で行いやすくなります。
試験ではどう問われるか
基本情報技術者試験では、優先度付きキューやヒープは、木構造や計算量と関連して問われることがあります。
まず押さえたいのは、優先度付きキューが「優先度の高い要素から取り出す」データ構造であることです。普通のキューのように、必ず先に入ったものから取り出すわけではありません。
ヒープについては、親子関係を追う問題が考えられます。最小ヒープなら、親の値は子の値以下です。根には最小値が来るため、次に取り出す値を判断できます。
また、配列でヒープを表すときの親子の位置も重要です。左の子、右の子、親のインデックスを計算できると、図がなくても構造を追いやすくなります。
試験では、優先度付きキューの取り出し順、ヒープの親子関係、追加や削除後の再構成が重要です。
実務ではどう使われるか
Web開発で、優先度付きキューを自分で毎日書くことは多くありません。ただし、考え方が使われる場面はあります。
たとえば、重要度の高いジョブを先に処理する、通知を優先度順に処理する、期限が近いタスクを先に取り出す、といった場面です。
また、経路探索やスケジューリングのアルゴリズムでも、優先度付きキューが登場します。最短距離が小さい候補から処理するような場面では、優先度付きキューが自然に使われます。
JavaScriptの標準機能には、専用の優先度付きキューはありません。そのため、実務ではライブラリを使うか、用途に合わせて簡単な実装を書くことがあります。仕組みを理解していると、ライブラリの挙動や計算量も読みやすくなります。
優先度付きキューは、重要度や期限に応じて次に処理するものを選びたい場面で役立ちます。
まとめ: 優先度付きキューは「次に処理すべきもの」を選ぶ道具
優先度付きキューは、入った順番ではなく、優先度に従って要素を取り出すデータ構造です。普通のキューが先入れ先出しであるのに対して、優先度付きキューは「どれを先に処理すべきか」を基準にします。
ヒープは、優先度付きキューを効率よく実装する代表的なデータ構造です。親子関係を保つことで、最も優先度の高い要素を根に置き、追加や取り出しを O(log n) で行いやすくします。
キュー、木構造、配列、計算量をつなげて理解できる点でも、優先度付きキューとヒープは重要な題材です。
優先度付きキューとヒープを理解すると、単に順番に処理するだけでなく、重要度に応じて処理順を決める設計を考えやすくなります。
コメント