python - heapq モジュール python

Question

モジュールを使用してheapq、リスト内の最小の項目を決定しています。

以下のコードがありますが、heapq.heapify()戻り値は None です。

新しいリストで結果を取得するにはどうすればよいですか?

>>> a=heapq.heapify(lista)
>>> a
>>> lista=[1,2,3,4,5]
>>> a=heapq.heapify(lista)
>>> print(a)
None

Answer 1

heapq.heapify何も返さず、リストを所定の位置にヒープ化します。そのようにする方がはるかに効率的です。

>>> import heapq
>>> lista = [44, 42, 3, 89, 10]
>>> heapq.heapify(lista)
>>> lista
[3, 10, 44, 89, 42]

新しいリストが必要な場合は、最初にコピーを作成します。

>>> lista = [44, 42, 3, 89, 10]
>>> newlist = lista[:]
>>> heapq.heapify(newlist)
>>> lista
[44, 42, 3, 89, 10]
>>> newlist
[3, 10, 44, 89, 42]

もちろん、リストのコピーには（線形の）コストもかかるため、これは目的をいくらか無効にします。

必要なのはリスト内の最小の項目だけである場合、min()関数は最小の要素を 1 つだけ見つけた場合と同じように高速heapify()になります (両方ともmin()入力リストを 1 回スキャンするため、O(n) のコストがかかります)。

>>> min(lista)
3

複数の最小値が必要な場合heapq、特に後で項目を追加する場合は、必ず を使用してください。元のリストを変更できず、いくつかの最小項目が必要な場合は、固定数の最小値のみを持つ入力ヒープから新しいヒープを作成する効率的な実装について、python で逆ヒープを探すを参照してください。nsmallest