Python の heapq モジュールについて-Python チュートリアル-php.cn

Python の heapq モジュールについて

Susan Sarandon

リリース： 2024-09-19 18:16:31

オリジナル

668 人が閲覧しました

Understanding Python

Python では、ヒープは、最小 (または最大) の項目に素早くアクセスする必要がある要素のコレクションを効率的に管理するための強力なツールです。

Python の heapq モジュールは、優先キューアルゴリズムとも呼ばれるヒープキューアルゴリズムの実装を提供します。

このガイドでは、ヒープの基本と heapq モジュールの使用方法を説明し、いくつかの実践的な例を示します。

ヒープとは何ですか?

ヒープは、次のヒーププロパティを満たす特別なツリーベースのデータ構造です。

最小ヒープでは、任意のノード I について、I の値はその子の値以下になります。したがって、最小の要素は常にルートにあります。
最大ヒープでは、I の値はその子の値以上であり、最大の要素がルートになります。

Python では、heapq は最小ヒープを実装します。これは、最小の要素が常にヒープのルートにあることを意味します。

ヒープを使用する理由

ヒープは、次のような場合に特に役立ちます。

最小または最大の要素への高速アクセス: ヒープ内の最小または最大の項目へのアクセスは O(1) です。つまり、一定時間で完了します。
効率的な挿入と削除: ヒープへの要素の挿入または最小要素の削除には O(log n) 時間がかかり、並べ替えられていないリストに対する操作よりも効率的です。

heapq モジュール

heapq モジュールは、通常の Python リストに対してヒープ操作を実行する関数を提供します。

使用方法は次のとおりです:

ヒープの作成

ヒープを作成するには、空のリストから開始し、heapq.heappush() 関数を使用して要素を追加します。

import heapq

heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 20)

ログイン後にコピー

これらの操作の後、ヒープは [5, 10, 20] になり、最小要素はインデックス 0 になります。

最小要素へのアクセス

最小の要素は、heap[0]:
を参照するだけで、削除せずにアクセスできます。

smallest = heap[0]
print(smallest)  # Output: 5

ログイン後にコピー

最小要素のポップ

最小の要素を削除して返すには、heapq.heappop():
を使用します。

smallest = heapq.heappop(heap)
print(smallest)  # Output: 5
print(heap)  # Output: [10, 20]

ログイン後にコピー

この操作の後、ヒープは自動的に調整され、次に小さい要素がルート位置になります。

リストをヒープに変換する

要素のリストがすでにある場合は、heapq.heapify():
を使用してそれをヒープに変換できます。

numbers = [20, 1, 5, 12, 9]
heapq.heapify(numbers)
print(numbers)  # Output: [1, 9, 5, 20, 12]

ログイン後にコピー

ヒープ化後の数値は [1, 9, 5, 12, 20] となり、ヒープのプロパティは維持されます。

複数のヒープのマージ

heapq.merge() 関数を使用すると、複数の並べ替えられた入力を 1 つの並べ替えられた出力にマージできます。

heap1 = [1, 3, 5]
heap2 = [2, 4, 6]
merged = list(heapq.merge(heap1, heap2))
print(merged)  # Output: [1, 2, 3, 4, 5, 6]

ログイン後にコピー

これにより、[1、2、3、4、5、6] が生成されます。

N 個の最大または最小の要素を見つける

heapq.nlargest() と heapq.nsmallest() を使用して、データセット内の最大または最小の n 要素を見つけることもできます。

numbers = [20, 1, 5, 12, 9]
largest_three = heapq.nlargest(3, numbers)
smallest_three = heapq.nsmallest(3, numbers)
print(largest_three)  # Output: [20, 12, 9]
print(smallest_three)  # Output: [1, 5, 9]

ログイン後にコピー

最大の 3 は [20, 12, 9]、最小の 3 は [1, 5, 9] になります。

実践例: 優先キュー

ヒープの一般的な使用例の 1 つは、各要素に優先順位があり、最も高い優先順位 (最も低い値) を持つ要素が最初に処理される優先キューの実装です。

import heapq


class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]


# Usage
pq = PriorityQueue()
pq.push('task1', 1)
pq.push('task2', 4)
pq.push('task3', 3)

print(pq.pop())  # Outputs 'task1'
print(pq.pop())  # Outputs 'task3'

ログイン後にコピー

この例では、タスクはそれぞれの優先順位で優先キューに格納されます。

優先度の値が最も低いタスクが常に最初にポップされます。