Pythonのheapqモジュールとは何ですか？

質問

私は "heapq"。 を試してみましたが、私の期待と画面に表示されるものが異なるという結論に達しました。私は、それがどのように動作し、どこで役に立つのかを説明するために誰かを必要としています。

書籍より 今週のPythonモジュール 段落下 2.2 並べ替え と書かれています。

値を追加したり削除したりするときに、ソートされたリストを維持する必要がある場合。 heapqをチェックしてみてください。heapqの関数を使用して、リストに項目を追加したり削除したりすることで の関数を使用することで、リストのソート順を維持することができます。 オーバーヘッドを低く抑えることができます。

以下は、私がやって得るものです。

import heapq
heap = []

for i in range(10):
    heap.append(i)

heap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

heapq.heapify(heap)    
heapq.heappush(heap, 10)    
heap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

heapq.heappop(heap)
0    
heap
[1, 3, 2, 7, 4, 5, 6, 10, 8, 9] <<< Why the list does not remain sorted?

heapq.heappushpop(heap, 11)
1
heap
[2, 3, 5, 7, 4, 11, 6, 10, 8, 9] <<< Why is 11 put between 4 and 6?

このように、quot;heap" のリストは全くソートされておらず、実際、項目を追加したり削除したりすればするほど、より乱雑になります。押し出された値は説明のつかない位置にあります。 何が起こっているのでしょうか？

どのように解決するのですか?

この heapq モジュールは ヒープ不変量 これは、実際のリストオブジェクトをソートされた順序で維持することと同じことではありません。

からの引用です。 heapq ドキュメント :

ヒープとは、すべての親ノードがその子ノード以下の値を持つ二分木のことです。この実装では heap[k] <= heap[2*k+1] と heap[k] <= heap[2*k+2] に対して、すべての k で、0から要素を数える。比較のために、存在しない要素は無限とみなされる。ヒープの興味深い性質は、その最小の要素が常にルートであることである。 heap[0] .

これは、最小の要素を見つけるのが非常に効率的であることを意味します（単に heap[0] を取るだけです)、これは優先キューにとって素晴らしいことです。その後、次の 2 つの値は 1 番目よりも大きく（または等しく）なり、その次の 4 つはその「親」ノードよりも大きくなり、その次の 8 つはより大きくなる、などです。

データ構造の背後にある理論について、より詳しく読むことができます。 理論セクションをご覧ください。 . また MIT OpenCourseWare Introduction to Algorithmsコースからのこの講義を見ることもできます。 の講義を見ることもできます。この講義では、アルゴリズムを一般的な用語で説明しています。

ヒープは非常に効率的にソートされたリストに戻すことができます。

def heapsort(heap):
    return [heapq.heappop(heap) for _ in range(len(heap))]

のように、ヒープから次の要素を読み出すだけでよいのです。使用する sorted(heap) を使うと、Python のソートで使われる TimSort アルゴリズムがヒープにすでに存在する部分的な順序付けを利用するので、しかし、より速くなるはずです。

最小の値にしか興味がない場合はヒープを使うでしょうし、最初の n 新しいアイテムを追加し、最小のものを削除することは、値を追加するたびにリストを再利用するよりも、実に効率的です。