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()功能将是一样快的定位只是一个最小的元素时(包括heapify()与min()扫描输入列表一次,所以O(n)的费用):

>>> min(lista)
3

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