リスト

[Python] heapq(優先度付きキュー)の使い方をわかりやすく解説

Pythonのheapqモジュールは、ヒープ(優先度付きキュー)を扱うための機能を提供します。

ヒープは常に最小値(または最大値)を効率的に取得できるデータ構造です。

heapq.heappush(heap, item)で要素を追加し、heapq.heappop(heap)で最小値を取り出します。

リストをヒープとして扱うため、事前にheapq.heapify(list)でヒープ化が必要です。

最大値を扱う場合は、値を負にして格納する方法が一般的です。

目次から探す

heapqとは？

heapqは、Pythonの標準ライブラリに含まれるモジュールで、ヒープ(優先度付きキュー)を実装するための機能を提供します。

ヒープは、特定の条件に基づいて要素を優先順位で管理するデータ構造で、最小値または最大値を効率的に取得することができます。

heapqを使用することで、リストをヒープとして扱い、要素の追加や削除を簡単に行うことができます。

ヒープの特徴

最小ヒープ: 最小値が常にルートに位置する。
効率的な操作: 要素の追加や削除がO(log n)の時間で行える。
順序の維持: ヒープの特性により、要素の順序が自動的に維持される。

heapqは、特に優先度付きキューを実装する際に非常に便利で、タスクのスケジューリングやダイクストラ法などのアルゴリズムで広く利用されています。

heapqの基本操作

heapqモジュールを使用することで、ヒープの基本的な操作を簡単に行うことができます。

以下に、主な操作とその使い方を示します。

ヒープの作成

リストをヒープに変換するには、heapify関数を使用します。

これにより、リストが最小ヒープの特性を持つように再配置されます。

import heapq
# リストを作成
numbers = [5, 3, 8, 1, 2]
# ヒープに変換
heapq.heapify(numbers)
# ヒープの状態を表示
print(numbers)

[1, 2, 8, 5, 3]

要素の追加

ヒープに要素を追加するには、heappush関数を使用します。

これにより、ヒープの特性が維持されます。

import heapq
# ヒープを作成
heap = [1, 2, 8, 5, 3]
heapq.heapify(heap)
# 要素を追加
heapq.heappush(heap, 4)
# ヒープの状態を表示
print(heap)

[1, 2, 4, 5, 3, 8]

最小要素の取得

ヒープから最小要素を取得するには、heappop関数を使用します。

この関数は、最小要素を削除し、その値を返します。

import heapq
# ヒープを作成
heap = [1, 2, 4, 5, 3]
heapq.heapify(heap)
# 最小要素を取得
min_element = heapq.heappop(heap)
# 最小要素とヒープの状態を表示
print("最小要素:", min_element)
print("ヒープの状態:", heap)

最小要素: 1
ヒープの状態: [2, 3, 4, 5]

ヒープの状態を確認

ヒープの状態を確認するには、単にリストを表示することで、現在のヒープの構造を確認できます。

ヒープの特性に従って、最小要素がルートに位置していることがわかります。

これらの基本操作を理解することで、heapqを使った優先度付きキューの実装が容易になります。

応用的な使い方

heapqモジュールは、基本的な操作だけでなく、さまざまな応用的な使い方が可能です。

以下にいくつかの具体例を示します。

N個の最小要素を取得する

リストからN個の最小要素を効率的に取得するには、nsmallest関数を使用します。

これにより、指定した数の最小要素を簡単に取得できます。

import heapq
# リストを作成
numbers = [5, 3, 8, 1, 2, 7, 4]
# N個の最小要素を取得
n_smallest = heapq.nsmallest(3, numbers)
# 結果を表示
print("最小の3つの要素:", n_smallest)

最小の3つの要素: [1, 2, 3]

N個の最大要素を取得する

同様に、リストからN個の最大要素を取得するには、nlargest関数を使用します。

これにより、指定した数の最大要素を簡単に取得できます。

import heapq
# リストを作成
numbers = [5, 3, 8, 1, 2, 7, 4]
# N個の最大要素を取得
n_largest = heapq.nlargest(3, numbers)
# 結果を表示
print("最大の3つの要素:", n_largest)

最大の3つの要素: [8, 7, 5]

優先度付きキューの実装

heapqを使用して、優先度付きキューを実装することも可能です。

タプルを使って、優先度と要素を組み合わせることで、優先度に基づいて要素を管理できます。

import heapq
# 優先度付きキューを作成
priority_queue = []
# 要素を追加(優先度, 要素)
heapq.heappush(priority_queue, (2, 'タスク2'))
heapq.heappush(priority_queue, (1, 'タスク1'))
heapq.heappush(priority_queue, (3, 'タスク3'))
# 優先度に基づいて要素を取得
while priority_queue:
    priority, task = heapq.heappop(priority_queue)
    print(f"優先度: {priority}, 実行するタスク: {task}")

優先度: 1, 実行するタスク: タスク1
優先度: 2, 実行するタスク: タスク2
優先度: 3, 実行するタスク: タスク3

スライディングウィンドウの最小値

スライディングウィンドウの最小値を求める際にもheapqを活用できます。

ウィンドウ内の最小値を効率的に管理することで、リアルタイムでの最小値取得が可能です。

これらの応用的な使い方を理解することで、heapqを利用したさまざまなアルゴリズムやデータ処理が可能になります。

実践例：heapqを使った具体的な活用シーン

heapqモジュールは、さまざまな実践的なシーンで活用できます。

以下に、具体的な活用例をいくつか紹介します。

タスクスケジューリング

タスクの優先度に基づいて実行順序を決定するために、heapqを使用してタスクスケジューリングを行うことができます。

タスクには優先度を設定し、優先度が高いものから順に実行します。

import heapq
# タスクのリスト(優先度, タスク名)
tasks = [
    (3, 'タスクC'),
    (1, 'タスクA'),
    (2, 'タスクB')
]
# 優先度付きキューを作成
priority_queue = []
for task in tasks:
    heapq.heappush(priority_queue, task)
# タスクを優先度に基づいて実行
while priority_queue:
    priority, task = heapq.heappop(priority_queue)
    print(f"実行するタスク: {task} (優先度: {priority})")

実行するタスク: タスクA (優先度: 1)
実行するタスク: タスクB (優先度: 2)
実行するタスク: タスクC (優先度: 3)

最小コストの経路探索

ダイクストラ法などの経路探索アルゴリズムにおいて、heapqを使用して最小コストの経路を効率的に見つけることができます。

以下は、簡単な例です。

import heapq
# グラフの定義(隣接リスト形式)
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
def dijkstra(graph, start):
    # 最小コストを保持する辞書
    min_cost = {node: float('inf') for node in graph}
    min_cost[start] = 0
    priority_queue = [(0, start)]
    while priority_queue:
        current_cost, current_node = heapq.heappop(priority_queue)
        for neighbor, cost in graph[current_node].items():
            new_cost = current_cost + cost
            if new_cost < min_cost[neighbor]:
                min_cost[neighbor] = new_cost
                heapq.heappush(priority_queue, (new_cost, neighbor))
    return min_cost
# 結果を表示
result = dijkstra(graph, 'A')
print("最小コスト:", result)

最小コスト: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

ストリーミングデータの処理

リアルタイムでデータを処理する際に、heapqを使用して最新のN個のデータを保持することができます。

例えば、ストリーミングデータから最新のN個の最大値を取得する場合です。

import heapq
# ストリーミングデータの例
streaming_data = [5, 1, 8, 3, 7, 2, 6, 4]
# 最新のN個の最大値を保持するためのヒープ
N = 3
max_heap = []
for number in streaming_data:
    heapq.heappush(max_heap, number)
    if len(max_heap) > N:
        heapq.heappop(max_heap)
# 最新のN個の最大値を表示
print("最新の3つの最大値:", max_heap)