Python で最大ヒープを取得
ヒープは、優先キューを実装するために選択されるデータ構造です。二分探索木とは異なり、ヒープは完全に順序付けられていません。兄弟やいとこの間に明確な順序はありません。
Python では、heapq モジュールがヒープキューアルゴリズムを実装します。ただし、heapq は最小ヒープの実装のみを提供します。この実装では、親ノードの値がその子の値のいずれか以下になります。
メイン関数 heappop() は、ヒープの最小要素を返します。
この記事では、heapq をいくつかのカスタムコードと組み合わせて、Python で最大ヒープ動作を実装する方法について説明します。
Python で数値を使用して最大ヒープを取得する
数値を処理する際の最も一般的な戦略は、リストの要素に-1 を掛けることです。heapq 関数はヒープを処理できます。
最小値をポップした後、最大値を取得するには、出力に-1 を再度乗算する必要があります。
サンプルコード：
# import the heapq module.
import heapq
# Max Heap With Numbers
# Create a list.
x = [5, 4, 3, 6, 8, 7, 2, 1]
# Print the list.
print(x)
# Multiply elements by -1.
x_inv = [-1 * i for i in x]
print(x_inv)
# Make the heap.
heapq.heapify(x_inv)
# Pop the maximum value.
# RUN ONE LINE AT A TIME.
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)
出力：
print(x)
[5, 4, 3, 6, 8, 7, 2, 1]
print(x_inv)
[-5, -4, -3, -6, -8, -7, -2, -1]
-1 * heapq.heappop(x_inv)
Out[8]: 8
-1 * heapq.heappop(x_inv)
Out[9]: 7
-1 * heapq.heappop(x_inv)
Out[10]: 6
Python でタプルを使用して最大ヒープを取得する
数字だけでなくタプルを使用して優先キューを実装したい場合があります。Python のタプルは不変であるため、これは優先順位の数値に-1 を掛ける作業への挑戦です。
解決策は、最初に各タプルをリストに変換し、これらのサブリストの最初の要素を-1 で変更し、それらをタプルに変換して戻し、同時にこれらのタプルを使用して新しいリストを作成することです。次に、heapify() を使用して、新しいリストがヒープに変換されます。
最大値をポップするには、ヒープで heappop() を使用し、タプルをリストに変換し、最初の要素を変更して正の値を取得してから、リストをタプルに変換し直します。
サンプルコード：
# Max Heap With Tuples
# Make a list of tuples.
l = [(1, "A"), (5, "B"), (3, "C"), (7, "D"), (6.5, "E")]
# View the list.
l
# Create an empty list to hold modified tuples.
l_max = []
# Populate the list with modified tuples.
for i in range(len(l)):
j = list(l[i])
j[0] = -1 * j[0]
l_max.append(tuple(j))
# View the modified list.
l_max
# Create the min heap.
heapq.heapify(l_max)
# View the min-heap.
l_max
# Create a function that uses meappop and
# changes the number back to a positive value.
def maxpop(mh):
l = list(heapq.heappop(mh))
l[0] = -1 * l[0]
return tuple(l)
# Test the values popped by the maxpop.
# RUN ONE LINE AT A TIME.
maxpop(l_max)
maxpop(l_max)
maxpop(l_max)
出力：
l
Out[15]: [(1, 'A'), (5, 'B'), (3, 'C'), (7, 'D'), (6.5, 'E')]
l_max
Out[14]: [(-1, 'A'), (-5, 'B'), (-3, 'C'), (-7, 'D'), (-6.5, 'E')]
heapq.heapify(l_max)
l_max
Out[17]: [(-7, 'D'), (-6.5, 'E'), (-3, 'C'), (-5, 'B'), (-1, 'A')]
maxpop(l_max)
Out[19]: (7, 'D')
maxpop(l_max)
Out[20]: (6.5, 'E')
maxpop(l_max)
Out[21]: (5, 'B')
他の必要なヒープ関数は、同じ手法を使用して実装できます。
参考文献
詳細と例については、Python の heapq モジュールのドキュメントを参照してください。
Python 開発チームは、最大ヒープ関数を実装しないことを決定しました。機能のリクエストとレスポンスはこちらで読むことができます。
Jesse is passionate about data analysis and visualization. He uses the R statistical programming language for all aspects of his work.