Python-data-structure-python-heaps
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]