Pythonのヒープキュー（またはheapq）

ヒープキューは、各親ノードがその子ノード以下である特別なツリー構造です。 Pythonでは、heapqモジュールを使用して実装されます。重みの高いキューアイテムの処理が優先される優先キューを実装すると非常に便利です。

ヒープを作成する

ヒープキューは、heapqという名前のPythonの組み込みライブラリを使用して作成されます。このライブラリには、ヒープデータ構造に対してさまざまな操作を実行するための関連関数があります。以下はこれらの機能のリストです。

• ヒープ化 –この関数は、通常のリストをヒープに変換します。結果のヒープでは、最小の要素がインデックス位置0にプッシュされます。ただし、残りのデータ要素は必ずしもソートされていません。
• heappush –この関数は、現在のヒープを変更せずに、ヒープに要素を追加します。
• ヒープ –この関数は、ヒープから最小のデータ要素を返します。
• heapreplace –この関数は、最小のデータ要素を関数で指定された新しい値に置き換えます。

ヒープの作成

ヒープは、heapify関数で要素のリストを使用するだけで作成されます。以下の例では、要素のリストを提供し、heapify関数が要素を再配置して、最小の要素を最初の位置に移動します。

例

import heapq
H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)

出力

上記のコードを実行すると、次の結果が生成されます-

[1, 3, 5, 78, 21, 45]

ヒープへの挿入

データ要素をヒープに挿入すると、常に最後のインデックスに要素が追加されます。ただし、heapify関数を再度適用して、値が最小の場合にのみ、新しく追加された要素を最初のインデックスに移動できます。以下の例では、番号8を挿入します。

例

import heapq
H = [21,1,45,78,3,5]
# Covert to a heap
heapq.heapify(H)
print(H)
# Add element
heapq.heappush(H,8)
print(H)

出力

上記のコードを実行すると、次の結果が生成されます-

[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]

ヒープからの削除

この関数を使用すると、最初のインデックスで要素を削除できます。次の例では、関数は常にインデックス位置1の要素を削除します。

例

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Remove element from the heap
heapq.heappop(H)

print(H)

出力

上記のコードを実行すると、次の結果が生成されます-

[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]

ヒープ内での置き換え

heapreplace関数は、常にヒープの最小要素を削除し、順序によって固定されていない場所に新しい入力要素を挿入します。

例

import heapq
H = [21,1,45,78,3,5]
# Create the heap
heapq.heapify(H)
print(H)
# Replace an element
heapq.heapreplace(H,6)
print(H)

出力

上記のコードを実行すると、次の結果が生成されます-

[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]