Python の heapq 組み込みモジュールの概要についての深い理解

heapq は python の組み込みモジュールです。ソース コードは Lib/heapq.py にあります。このモジュールは、ヒープベースの優先順位付けアルゴリズムを提供します。

ヒープの論理構造は完全なバイナリ ツリーであり、バイナリ ツリー内の親ノードの値は、そのノードのすべての子ノードの値以下です。この実装は、heap[k] index) の形式で具体化できます。 for ヒープに関して言えば、最小の要素はルート要素 heap[0] です。

listを介してヒープを初期化することも、apiのheapifyを介して既知のリストをヒープオブジェクトに変換することもできます。

heapq はfunctionメソッドを提供します

heapq.heappush(heap, item)

heapq.heappop(heap): ヒープ内の最小要素であるルートノードを返します

heapq.heappushpop(heap, item) : item 要素をヒープに追加し、ヒープ内の最小要素を返します

heapq.heapify(x)

heapq.nlargest(n, iterable, key=None): 内の最大 n 個の値を返します列挙可能なオブジェクトを返し、結果セットリストを返します。キーは結果セットに対する操作です

heapq.nsmallest(n, iterable, key=None): 上記と同じで、その逆です

demo

1. heapq APIを通じてリストがソートされます

def heapsort(iterable):
    h = []

    for i in iterable:
        heapq.heappush(h, i)

    return [heapq.heappop(h) for i in range(len(h))]


s = [3, 5, 1, 2, 4, 6, 0, 1]
print(heapsort(s))

出力は次のようになります

 [0, 1, 1, 2, 3, 4, 5, 6]

2. キーを通してオブジェクトリスト内の最小価格のアイテムを検索します

portfolio = [
    {'name': 'IBM', 'shares': 100, 'price': 91.1},
    {'name': 'AAPL', 'shares': 50, 'price': 543.22},
    {'name': 'FB', 'shares': 200, 'price': 21.09},
    {'name': 'HPQ', 'shares': 35, 'price': 31.75},
    {'name': 'YHOO', 'shares': 45, 'price': 16.35},
    {'name': 'ACME', 'shares': 75, 'price': 115.65}
]
cheap = heapq.nsmallest(1, portfolio, key=lambda s: s['price'])
print(cheap)

出力は次のようになります

[{'shares': 45, 'price': 16.35, 'name': 'YHOO'}]

extend

上で述べたように、heapq は最小ヒープの実装です。 heapq のソースコード (親ノードのキーワードは左右の子ノードより小さい)

はい 以下のステップに分かれています:

1. 子ノードを持つ最後の要素から始めて、この親ノードを扱います。要素とその子ノードをユニット化します

2. 2つの子ノードのうち小さい方をユニット内に追加します要素と親ノードの位置を交換します(親ノードと最小の子ノードの大小関係を判断する必要はありません)このステップにより、この単位は最小ヒープ単位に変更できます

3. while ループにより、より大きな単位が変更できます 小さな要素が押し上げられます

def heapilize_list(x):
    n = len(x)
    # 获取存在子节点的节点 index 列表，并对每个节点单元进行最小堆处理
    for i in reversed(range(n // 2)):
        raiseup_node(x, i)

def put_down_node(heap, startpos, pos):
    current_item = heap[pos]
    # 判断单元中最小子节点与父节点的大小
    while pos > startpos:
        parent_pos = (pos - 1) >> 1
        parent_item = heap[parent_pos]

        if current_item < parent_item:
            heap[pos] = parent_item
            pos = parent_pos
            continue
        break

    heap[pos] = current_item

def raiseup_node(heap, pos):
    heap_len = len(heap)
    start_pos = pos
    current_item = heap[pos]
    left_child_pos = pos * 2 + 1

    while left_child_pos < heap_len:
        right_child_pos = left_child_pos + 1
        # 将这个单元中的最小子节点元素与父节点元素进行位置调换
        if right_child_pos < heap_len and not heap[left_child_pos] < heap[right_child_pos]:
            left_child_pos = right_child_pos
        heap[pos] = heap[left_child_pos]
        pos = left_child_pos
        left_child_pos = pos * 2 + 1
    heap[pos] = current_item
    put_down_node(heap, start_pos, pos)


p = [4, 6, 2, 10, 1]
heapilize_list(p)
print(p)

出力は次のとおりです

りー

以上がPython の heapq 組み込みモジュールの概要についての深い理解の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。