python - python中的最小堆

Question

我想通过定义自定义比较函数将一组对象存储在最小堆中。我看到有一个 heapq 模块作为 python 发行版的一部分可用。有没有办法在这个模块中使用自定义比较器？如果没有，是否有人构建了自定义最小堆？

Answer 1

两个选项(除了 Devin Jeanpierre 的建议):

1. 在使用堆之前修饰您的数据。这相当于排序的 key= 选项。例如如果您(出于某种原因)想根据正弦值来堆砌数字列表:

   data = [ # list of numbers ]
   heap = [(math.sin(x), x) for x in data]
   heapq.heapify(heap)
   # get the min element
   item = heappop(heap)[1]
   

2. heapq 模块是用纯 python 实现的。您可以将它复制到您的工作目录并更改相关位。快速浏览一下，您将不得不修改 siftdown() 和 siftup()，如果需要，可能还需要修改 nlargest 和 nsmallest。