当前位置：文江博客话题详情

python 中的最小堆

发布于 2024-07-16 05:02:24 字数 113 浏览 15 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

友欢 2024-07-23 05:02:24

有两个选项（除了 Devin Jeanpierre 的建议）：

在使用堆之前装饰您的数据。这相当于排序的 key= 选项。例如，如果您（出于某种原因）想根据正弦值堆积数字列表：

data = [ # 数字列表 ] 
  堆 = [(math.sin(x), x) 对于数据中的 x] 
  heapq.heapify(堆) 
  # 获取最小元素 
  项目 = heappop(堆)[1]

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

Two options (aside from Devin Jeanpierre's suggestion):

Decorate your data before using the heap. This is the equivalent of the key= option to sorting. e.g. if you (for some reason) wanted to heapify a list of numbers according to their sine:
```
data = [ # list of numbers ]
heap = [(math.sin(x), x) for x in data]
heapq.heapify(heap)
# get the min element
item = heappop(heap)[1]
```
The heapq module is implemented in pure python. You could just copy it to your working directory and change the relevant bits. From a quick look, you would have to modify siftdown() and siftup(), and possibly nlargest and nsmallest if you need them.

回复收藏 0 原文

○闲身 2024-07-23 05:02:24

是的，有办法。定义一个实现自定义比较器的包装类，并使用这些比较器的列表而不是实际对象的列表。这是在仍然使用 heapq 模块时最好的，因为它没有像排序函数/方法那样提供 key= 或 cmp= 参数。

def gen_wrapper(cmp):
    class Wrapper(object):
        def __init__(self, value): self.value = value
        def __cmp__(self, obj): return cmp(self.value, obj.value)
    return Wrapper

Yes, there is a way. Define a wrapping class that implements your custom comparator, and use a list of those instead of a list of your actual objects. That's about the best there is while still using the heapq module, since it provides no key= or cmp= arguments like the sorting functions/methods do.

def gen_wrapper(cmp):
    class Wrapper(object):
        def __init__(self, value): self.value = value
        def __cmp__(self, obj): return cmp(self.value, obj.value)
    return Wrapper

回复收藏 0 原文

~没有更多了~