heappq:スタックアルゴリズム
1495 ワード
heappq:スタックアルゴリズム
Source code:Lib/heappq.py
紹介するこのモジュールは、キュー・アルゴリズムの実装を提供し、優先キュー・アルゴリズムとも称する. ヒープは特殊な二叉樹(本文書では小頂部のヒープに対応して大きな山があります)であり、その親の各接合点の値はその子供二人の接合点の値より小さいです.この文のヒープは、配列に基づいて実現される静的な二叉樹であり、配列内の各要素 については、並べ替えられた複数のシーケンス(昇順)を統合し、反復可能なオブジェクト を返します.機能は、 には2つのオプションパラメータがあります. keyパラメータは、入力シーケンスにおける並べ替えのための要素を指定するkey関数を定式化する. reverseはブックの値です.trueであれば、統合後の要素はegに並びます. スタックの順序付けは、すべての要素をスタックに押し込むことによって、その後、小さいときからトップスタックの中から最小の要素(すなわち、二叉ツリーのルートノード)を取り出すことができる: 上記の積み上げ順序と内蔵 スタックの要素は、元のグループとすることができる.これは、ジョブ優先度のように、ある属性を現在の比較値として選択するために使用することができる.
Source code:Lib/heappq.py
紹介する
heapq.merge(\*iterables, key=None, reverse=False)sorted(itertools.chain(*iterables))と同様であるが、すべてのデータを一度にメモリに入れないように反復可能なオブジェクトを返し、入力のシーケンスは順序付け、昇順を前提としなければならない.a = [3, 1, 5, 7]
b = [2, 4, 6, 8]
c = merge(a, b)
for item in c:
print(item, sep=" ", end=" "
output:
1 2 3 4 5 6 7 8
def heapsort(iterable):
h = []
for value in iterable:
heappush(h, value)
return [heappop(h) for i in range(len(h))]
heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
sorted(iterable)関数は似ていますが、この積み上げ順序は安定していません.sorted(iterable)は安定した順序です.h = []
heappush(h, (5, 'write code'))
heappush(h, (7, 'release product'))
heappush(h, (1, 'write spec'))
heappush(h, (3, 'create tests'))
heappop(h)