Python-ヒープ
ヒープは、各親ノードがその子ノード以下である特別なツリー構造です。それからそれは最小ヒープと呼ばれます。各親ノードがその子ノード以上である場合、それは最大ヒープと呼ばれます。重みの高いキューアイテムの処理が優先される優先キューを実装すると非常に便利です。ヒープの詳細については、こちらのWebサイトをご覧ください。ヘッドデータ構造に不慣れな場合は、最初にそれを研究してください。この章では、Pythonを使用したヒープデータ構造の実装について説明します。
ヒープを作成する
ヒープは、heapqという名前のPythonの組み込みライブラリを使用して作成されます。このライブラリには、ヒープデータ構造に対してさまざまな操作を実行するための関連関数があります。以下はこれらの関数のリストです。
- heapify-この関数は、通常のリストをヒープに変換します。結果のヒープでは、最小の要素がインデックス位置0にプッシュされます。ただし、残りのデータ要素は必ずしもソートされていません。
- heappush –この関数は、現在のヒープを変更せずに、ヒープに要素を追加します。
- heappop-この関数は、ヒープから最小のデータ要素を返します。
- 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]