python - heapq 模块 python

Question

我正在使用该heapq模块来确定列表中的最小项目。

我有下面的代码，但heapq.heapify()返回值为无。

如何在新列表中获得结果？

>>> 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()函数在仅定位一个最小元素时将同样快（同时扫描输入heapify()列表min()一次，因此 O(n) 成本）：

>>> min(lista)
3

如果您需要多个最小值，请务必使用 a heapq，尤其是稍后添加项目时。如果您无法更改原始列表，需要几个最小的项目，请参阅在 python 中寻找倒置堆以获得有效实现，该实现从只有固定数量的最小值nsmallest的输入堆创建新堆。

Answer 2

你必须使用 heapq.nsmallest(k,arr) 函数。//k 这里是 1，因为你想要一个最小值。

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