python中的堆heapq

python中并没有像java那样封装一个堆类。而是提供了一个heapq堆函数，它可以将list转化为堆。

heapq中的堆是最小堆！

heapq中拥有的函数：

• heapq.heapify(list)：将list转换成堆，直接对list进行修改，不返回值。
• heapq.heappush(heap, val)：将val添加进堆中。
  • 应注意！添加的数组应为堆数组（也就是heapify后的），如果是普通数组它添加时并不会按照你想的方式添加（因为添加是按照堆的规则添加的）。
• heapq.heappop(heap)：将堆中最小元素弹出，并返回该元素
  • 在弹出时，数组也应该为堆数组。所以除非我们当前的数组是堆数组，否则我们应在push、pop之前进行一次heapify。
• heapq.heapreplace(heap, val)：先进行pop，在进行push。
• heapq.heappushpop(heap, val)：先进行push，再进行pop，返回pop后的值。
  • 使用replace、pushpop要比，使用一遍push再使用pop要快。
• heapq.nlargest(n, heap)：查找堆中最大的n个元素
• heapq.nsmallest(n, heap)：查找堆中最小的n个元素

值得注意的是：如果你想要查大于一个的top元素可以使用nlargest、nsmallest。但是如果你只想查最大或最小的一个元素，直接用索引heap[0]查看，使用前者耗时会多！

heapq与自定义类型

你可以将自定义类型与优先度放在一个元组中，这样他会比较元组中的优先度来进行排序。

x = [(3, "x"), (1, "b"), (6, "z")]
heapq.heapify(x)
print(x)[(1, 'b'), (3, 'x'), (6, 'z')]

它是按照元组的顺序每个元素进行比较的，例如：

x = [(1, 1, "x"), (1, 2, "b"), (3, "z")]
heapq.heapify(x)
print(x)[(1, 1, 'x'), (1, 2, 'b'), (3, 'z')]

heapq实现最大堆

对于最大堆，可以将数组负数化（最小的就变成最大的了）作为优先度，原元素作为值进行堆化。