问题标签 [heapq]

我在阅读 Dijkstra 算法上的伪代码时遇到了一些麻烦：

到目前为止，我已经根据伪代码写了这么多：

然而，我现在被困在“ foreach neighbor v of u do ”这一行了。如何在 Python 中为“u 的邻居节点”解释这个 forloop？我不知道如何写这一行。蒂亚！

对于https://leetcode.com/problems/top-k-frequent-elements找到前 k 个频繁元素的问题，我知道我们可以使用 heapq.nlargest() 方法，但为此使用的键只是没有大括号的 dict.get -heapq.nlargest(k,count.keys(),key=count.get)

如果我们尝试打印 dict.get 它会返回对象，如果我们尝试使用不带键的 dict.get() 则会抛出错误。

那么有人可以解释一下使用不带大括号的 dict.get 作为键是什么意思吗？

问题

我有一个对象列表。每个对象都有两个属性：“score”和“coordinates”。我需要根据属性找到列表中最大的N个对象。score我遇到的主要问题是仅使用score属性对对象进行排序。排序可以是部分的。我只对N个最大的对象感兴趣。

当前解决方案

我目前的方法不是最优雅也不是最有效的。这个想法是创建一个dictionaryof 对象indices及其score，然后对分数列表进行排序并使用dictionary来索引产生最大分数的对象。

这些是步骤：

1. 创建一个列表scores。列表的每个元素对应一个对象。也就是说，第一个条目是第一个对象的分数，第二个条目是第二个对象的分数，依此类推。

2. dictionary使用对象的scoresaskey和对象indexas创建一个value。

3. 使用 a 对分数列表进行排序heapq以获得N最大的对象。

4. 使用dictionary获取具有最大 的那些对象scores。

5. list仅使用N最高分对象创建一个新对象。

代码片段

这是我的排序功能：

此片段生成100用于测试我的方法的随机对象。最后一个循环打印N = 3随机生成的最大对象score：

我目前的方法可以完成工作，但必须有一种更Pythonic（更矢量化）的方式来实现相同的目标。我的背景主要是 C++，我还在学习 Python。欢迎任何反馈。

附加信息

最初，我正在寻找类似于 C++ 的std:: nth_element. 似乎 NumPy 在 Python 中提供了此功能partition。不幸的是，虽然std::nth_element支持自定义排序的谓词，但 NumPypartition不支持。我最终使用了 a heapq，它可以很好地完成工作并按所需的顺序进行排序，但我不知道基于一个属性进行排序的最佳方式。

我正在解决 Interviewbit 代码挑战Merge K Sorted Lists：

合并 k 个排序的链表并将其作为一个排序列表返回。

例子 ：

将导致

Python 模板代码为：

这是我的python 3解决方案：

使用未注释的打印命令，您会注意到在 while 循环的中间运行中，heappop返回最大的元素，就好像我们正在处理一个最大堆，但我们不是！据我所知，这就是答案出错的地方。任何人都可以提出为什么 heappop 会这样工作的原因吗？以及如何纠正？

我有以下代码：

假设 huge_generator() 定义如下（当然，它的实际实现不允许将其内容一次全部保存在内存中）：

我的代码返回这个，到目前为止一切顺利：

现在我想将顺序自定义为升序、降序、降序。IE，

我不明白，也没有找到任何方法来指定自定义比较器来做我想做的事，这甚至可能吗？