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

- user1050619

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

如果你需要多个最小值，一定要使用一个 heapq，特别是如果你之后还会添加项。如果你不能修改原始列表，需要多个最小项，请查看在python中寻找一个反转堆的实现，以获得一个高效的 nsmallest 实现，它从输入堆中创建一个新的堆，只包含固定数量的最小值。

- Martijn Pieters

---

他可能不熟悉典型的堆实现和遍历。 - Joran Beasley

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

- Mayank Maheshwari