77

「heapq」を試してみたところ、私の期待は画面に表示されているものとは異なるという結論に達しました。それがどのように機能し、どこで役立つかを説明してくれる人が必要です。

パラグラフ2.2ソートの下の本Pythonモジュールオブザウィークから、それは書かれています

値を追加および削除するときにソートされたリストを維持する必要がある場合は、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?

したがって、ご覧のとおり、「ヒープ」リストはまったくソートされていません。実際、アイテムを追加および削除すればするほど、リストは雑然とします。プッシュされた値は、説明できない位置を取ります。何が起こっている？

4

4 に答える 4

109

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

heapqドキュメントからの引用：

ヒープは、すべての親ノードがその子のいずれか以下の値を持つバイナリ ツリーです。この実装では、要素を 0 から数えて、 whichheap[k] <= heap[2*k+1]およびheap[k] <= heap[2*k+2]all に対して配列を使用します。k比較のために、存在しない要素は無限であると見なされます。ヒープの興味深い特性は、その最小要素が常にルートであるということheap[0]です。

これは、最小の要素 (単に take heap[0]) を見つけるのが非常に効率的であることを意味し、これはプライオリティ キューに最適です。その後、次の 2 つの値は最初の値よりも大きく (または等しく) なり、その後の次の 4 つの値は「親」ノードよりも大きくなり、次の 8 つの値は大きくなります。

データ構造の背後にある理論の詳細については、ドキュメントの理論セクションを参照してください。この講義は、MIT OpenCourseWare Introduction to Algorithms コースからも視聴できます。このコースでは、アルゴリズムを一般的な用語で説明しています。

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

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

ヒープから次の要素をポップするだけです。ただし、Python の並べ替えで使用sorted(heap)される TimSort アルゴリズムは、ヒープに既に存在する部分的な順序付けを利用するため、使用はさらに高速になるはずです。

n最小値または最初の最小値のみに関心がある場合、特にこれらの値に継続的に関心がある場合は、ヒープを使用します。新しいアイテムを追加して最小のものを削除することは、値を追加するたびにリストを並べ替えるよりも、実際に非常に効率的です。

于 2013-11-14T14:03:47.787 に答える
39

あなたの本は間違っています！あなたが示すように、ヒープはソートされたリストではありません (ソートされたリストはヒープですが)。ヒープとは Skiena's Algorithm Design Manual を引用するには

ヒープは、優先キュー操作の挿入および抽出分を効率的にサポートするためのシンプルで洗練されたデータ構造です。それらは、ソートされた順序よりも弱い (維持するのが効率的である可能性があるため) が、ランダムな順序よりも強い (最小要素をすばやく識別できるようにするため) 要素のセットで部分的な順序を維持することによって機能します。

ソートされたリストと比較して、ヒープはヒープ不変条件というより弱い条件に従います。それを定義する前に、条件を緩和することがなぜ役立つのかをまず考えてください。答えは弱い方が維持しやすいです。ヒープでできることは少なくなりますが、より速く行うことができます。

ヒープには次の 3 つの操作があります。

  1. Find-Minimum は O(1)
  2. O(log n) を挿入
  3. 削除分 O(log n)

重要なことに、挿入は O(log n) であり、ソートされたリストの O(n) よりも優れています。

ヒープ不変条件とは何ですか? 「親が子を支配する二分木」。つまり、「p ≤ cp のすべての子 c に対して」です。Skiena は写真を使って説明し、不変条件を維持しながら要素を挿入するアルゴリズムを示します。少し考えれば、自分で発明することができます。(ヒント: バブルアップとバブルダウンとして知られています)

良いニュースは、バッテリーを含む Python がheapqモジュールですべてを実装していることです。ヒープタイプを定義しませんが（使いやすいと思います）、リストのヘルパー関数として提供します。

教訓:ソートされたリストを使用してアルゴリズムを作成し、一方の端からのみ検査して削除する場合は、ヒープを使用してアルゴリズムをより効率的にすることができます。

ヒープ データ構造が役立つ問題については、https://projecteuler.net/problem=500を参照してください。

于 2015-07-03T17:34:22.690 に答える
29

ヒープ データ構造の実装には誤解があります。このheapqモジュールは、実際には、 https: //en.wikipedia.org/wiki/Binary_heap#Heap_implementationで説明されているように、ヒープ要素がリストに格納されるバイナリ ヒープ実装の変形です。

ウィキペディアを引用：

ヒープは通常、配列で実装されます。任意のバイナリ ツリーを配列に格納できますが、バイナリ ヒープは常に完全なバイナリ ツリーであるため、コンパクトに格納できます。ポインター用のスペースは必要ありません。代わりに、各ノードの親と子は、配列インデックスの算術演算によって見つけることができます。

以下の画像は、ヒープのツリー表現とリスト表現の違いを感じるのに役立つはずです (これは最大ヒープであり、通常の最小ヒープの逆であることに注意してください! ):

ここに画像の説明を入力

一般に、ヒープ データ構造は、特定の要素が他の要素よりも大きいか小さいかに関する情報を犠牲にするという点で、並べ替えられたリストとは異なります。ヒープは、この特定の要素が親よりも小さく、子よりも大きいことしかわかりません。データ構造に保存される情報が少ないほど、変更にかかる時間/メモリが少なくなります。ヒープと並べ替えられた配列の間のいくつかの操作の複雑さを比較します。

        Heap                  Sorted array
        Average  Worst case   Average   Worst case

Space   O(n)     O(n)         O(n)      O(n)

Search  O(n)     O(n)         O(log n)  O(log n)

Insert  O(1)     O(log n)     O(n)      O(n)

Delete  O(log n) O(log n)     O(n)      O(n)
于 2013-11-14T14:03:58.147 に答える