ヒープ・スタック・キュー

要素の追加・削除順序が異なる3つのデータ構造。

ヒープ

常に最小（または最大）要素を素早く取り出せるデータ構造。優先度キューなどで使用される。

スタック

最後に追加した要素を最初に取り出すデータ構造（LIFO）。関数呼び出し履歴の管理などで使用される。

キュー

最初に追加した要素を最初に取り出すデータ構造（FIFO）。タスクキューなどで使用される。

優先度キュー

要素に優先度を持つキュー。優先度の高い要素から順に取り出される。

LIFO

Last In First Out。最後に追加した要素を最初に取り出す。

FIFO

First In First Out。最初に追加した要素を最初に取り出す。

計算量

アルゴリズムの実行時間を表す指標。

ヒープ

山

ヒープは「山」のようなもの。山の頂上には、最も高い（または最も低い）場所があります。頂上の要素を取り出すとき、すぐに次の高い（または低い）要素が頂上に来ます。これは、常に最小（または最大）要素を素早く取り出すのに適しています。

なぜヒープが必要か？

ヒープは、常に最小（または最大）要素を素早く取り出せるデータ構造です。優先度キュー、グラフアルゴリズム、ソートアルゴリズムなど、多くの場面で使用されます。特に、要素の追加・削除が頻繁で、常に最小（または最大）要素を取得する必要がある場合に適しています。

いつ使うか？

優先度キューを実装する場合
グラフアルゴリズム（ダイクストラ、プリム法など）を実装する場合
ソートアルゴリズムを実装する場合
常に最小（または最大）要素を取得する必要がある場合

実践テクニック

heapqモジュールを使う

Pythonの `heapq` モジュールは、ヒープ操作のための最適化された実装を提供しています。`heapq.heappush()` や `heapq.heappop()` を使うことで、効率的にヒープ操作を行うことができます。

カスタム比較関数を定義する

ヒープでオブジェクトを扱う場合、カスタム比較関数を定義することで、優先度を制御できます。`__lt__` メソッドを実装することで、オブジェクトの比較ロジックをカスタマイズできます。

計算量を理解する

ヒープの操作の計算量を理解することは、パフォーマンス最適化に重要です。例：要素の追加はO(log n)、最小値の取得はO(1)です。これらを理解して、適切なデータ構造を選択します。

1
# ヒープの基本操作
2
import heapq
3

4
# ヒープの作成
5
heap = []
6
heapq.heappush(heap, 5)
7
heapq.heappush(heap, 3)
8
heapq.heappush(heap, 8)
9
heapq.heappush(heap, 1)
10
print(heap)  # [1, 3, 5, 8]
11

12
# 最小値の取得
13
print(heapq.heappop(heap))  # 1
14

15
# 要素の削除
16
heapq.heappop(heap)
17
print(heap)  # [1, 3, 5, 8]

スタック

本の山

スタックは「本の山」のようなもの。本を山に積み上げていきます。本を取り出すときは、一番上の本から取ります。これは、最後に追加した要素を最初に取り出す（LIFO）動作を表しています。

なぜスタックが必要か？

スタックは、最後に追加した要素を最初に取り出すデータ構造です（LIFO）。関数呼び出し履歴の管理、式の評価、バックトラッキング、Undo/Redo機能など、多くの場面で使用されます。特に、後入れ先出し（LIFO）の動作が必要な場合に適しています。

いつ使うか？

関数呼び出し履歴を管理する場合
式の評価を行う場合
バックトラッキングを実装する場合
Undo/Redo機能を実装する場合

実践テクニック

listを使う

Pythonの `list` は、スタックとして使用できます。`append()` で要素を追加し、`pop()` で要素を削除します。`[-1]` でトップ要素を確認できます。

dequeを使う

`collections.deque` は、両端から効率的に要素を追加・削除できる両端キューです。スタックとして使用する場合、`append()` と `pop()` を使います。

計算量を理解する

スタックの操作の計算量を理解することは、パフォーマンス最適化に重要です。例：要素の追加はO(1)、要素の削除はO(1)です。これらを理解して、適切なデータ構造を選択します。

1
# スタックの基本操作
2
stack = []
3

4
# 要素の追加
5
stack.append(1)
6
stack.append(2)
7
stack.append(3)
8
print(stack)  # [1, 2, 3]
9

10
# 要素の削除（LIFO）
11
print(stack.pop())  # 3
12
print(stack)  # [1, 2]
13

14
# トップ要素の確認
15
print(stack[-1])  # 2

キュー

レストランの行列

キューは「レストランの行列」のようなもの。お客様が行列の最後尾に並び、順番にサービスを受けます。スタッフは行列の先頭からお客様を順にサービスします。これは、最初に追加した要素を最初に取り出す（FIFO）動作を表しています。

なぜキューが必要か？

キューは、最初に追加した要素を最初に取り出すデータ構造です（FIFO）。タスクキュー、メッセージキュー、イベント処理、バッファリングなど、多くの場面で使用されます。特に、先入れ先出し（FIFO）の動作が必要な場合に適しています。

いつ使うか？

タスクキューを実装する場合
メッセージキューを実装する場合
イベント処理を実装する場合
バッファリングを実装する場合

実践テクニック

queueモジュールを使う

Pythonの `queue` モジュールは、FIFOキューの実装を提供しています。ただし、`collections.deque` の方がパフォーマンスが良い場合が多いため、推奨されます。

dequeを使う

`collections.deque` は、両端から効率的に要素を追加・削除できる両端キューです。キューとして使用する場合、`append()` と `popleft()` を使います。スタックとして使用する場合、`append()` と `pop()` を使います。

計算量を理解する

キューの操作の計算量を理解することは、パフォーマンス最適化に重要です。例：要素の追加はO(1)、要素の削除はO(1)です。これらを理解して、適切なデータ構造を選択します。

1
# キューの基本操作
2
from collections import deque
3

4
queue = deque()
5

6
# 要素の追加
7
queue.append(1)
8
queue.append(2)
9
queue.append(3)
10
print(queue)  # deque([1, 2, 3])
11

12
# 要素の削除（FIFO）
13
print(queue.popleft())  # 1
14
print(queue)  # deque([2, 3])

計算量

ヒープ・スタック・キューの操作の計算量を比較する。

1
# ヒープの計算量
2
import heapq
3

4
heap = []
5
heapq.heappush(heap, 5)
6
heapq.heappush(heap, 3)
7
heapq.heappush(heap, 8)
8
heapq.heappush(heap, 1)
9

10
# 最小値の取得: O(1)
11
print(heapq.heappop(heap))
12

13
# 要素の追加: O(log n)
14
heapq.heappush(heap, 2)
15

16
# 要素の削除: O(log n)
17
heapq.heappop(heap)

1
# スタックの計算量
2
stack = []
3

4
# 要素の追加: O(1)
5
stack.append(1)
6

7
# 要素の削除: O(1)
8
stack.pop()
9

10
# トップ要素の確認: O(1)
11
print(stack[-1])

1
# キューの計算量
2
from collections import deque
3

4
queue = deque()
5

6
# 要素の追加: O(1)
7
queue.append(1)
8

9
# 要素の削除: O(1)
10
queue.popleft()

使用例

ヒープ・スタック・キューの実際の使用例を確認する。

1
# ヒープの使用例
2
# 優先度キューの実装
3
import heapq
4

5
class Task:
6
    def __init__(self, priority, description):
7
        self.priority = priority
8
        self.description = description
9

10
    def __lt__(self, other):
11
        return self.priority < other.priority
12

13
# タスクの追加
14
tasks = []
15
heapq.heappush(tasks, Task(1, "Low priority task"))
16
heapq.heappush(tasks, Task(3, "Medium priority task"))
17
heapq.heappush(tasks, Task(5, "High priority task"))
18

19
# タスクの実行
20
while tasks:
21
    task = heapq.heappop(tasks)
22
    print(f"Executing: {task.description}")
23
    # タスクの処理を行う
24
    # ...
25

26
# 使用例
27
# タスクを優先度順に実行

1
# スタックの使用例
2
# 関数呼び出しスタックの実装
3
call_stack = []
4

5
def process_function():
6
    call_stack.append("start")
7
    # 処理を行う
8
    call_stack.append("end")
9
    if call_stack[-1] == "end":
10
        call_stack.pop()
11
        # 関数が終了した
12

13
# 使用例
14
process_function()
15
process_function()
16
print(call_stack)  # []

1
# キューの使用例
2
# タスクキューの実装
3
from collections import deque
4

5
task_queue = deque()
6

7
# タスクの追加
8
task_queue.append("Task 1")
9
task_queue.append("Task 2")
10
task_queue.append("Task 3")
11

12
# タスクの実行
13
while task_queue:
14
    task = task_queue.popleft()
15
    print(f"Processing: {task}")
16
    # タスクの処理を行う
17
    # ...
18

19
# 使用例
20
# タスクを順番に実行

比較

ヒープ・スタック・キューの特徴を比較する。

特徴	ヒープ	スタック	キュー
要素の追加	O(log n)	O(1)	O(1)
要素の削除	O(log n)	O(1)	O(1)
最小/最大要素の取得	O(1)	O(1)	O(1)
順序	優先度順	LIFO	FIFO
主な用途	優先度キュー	関数呼び出し履歴	タスクキュー

合格ライン

☐ ヒープの基本操作ができる

☐ スタックの基本操作ができる

☐ キューの基本操作ができる

☐ ヒープ・スタック・キューの計算量を理解している

☐ ヒープ・スタック・キューの使い分けができる

演習課題

課題1: ヒープの基本操作

ヒープを作成し、要素を追加・削除・検索するコードを書いてください。

課題2: スタックの実装

スタッククラスを実装し、要素の追加・削除・走査を行うメソッドを作成してください。

課題3: キューの実装

キュークラスを実装し、要素の追加・削除・走査を行うメソッドを作成してください。

参考文献

この記事は以下の公的ガイドライン/標準に基づいています。

heapq Documentation - heapq モジュールドキュメント
deque Documentation - deque クラスドキュメント
Python Data Structures - 公式ドキュメント