问题标签 [heapq]

我想在这种情况下根据字典键“价格”列出字典列表中最大的两个和最小的两个项目 - 如下代码所示 - 使用 heapq 模块两个函数 nlargest() 和 nsmallest( ）我尝试了这段代码，但它没有用：

然后我找到了一个使用 lambda 的解决方案，它确实有效！但我不明白：这是包含解决方案的版本，它可以工作，但我不明白在这种情况下使用 lambda：

这正是我所期望的输出：

我希望在函数 nlargest 或 nsmallest 的参数键中找到使用 lambda 的一个很好的解释，并提前致谢。

在此之后，我应该如何插入 9 到实际位置，即第 0 个索引？

列表不需要 O(n) 时间来增加其大小吗？那么 heap.heappush 怎么可能是 O(log n) 呢？

来自 Java，我正在尝试在 python 中实现A* 算法，但我无法对图中 f 分数相等的顶点进行排序。我正在尝试使用 这样做heapq，经过一些调试后，我注意到如果我想推送一个 f 分数等于堆中其他一些预先存在的顶点的顶点，那么顺序就会混乱。我现在正在考虑实施我自己的优先级队列。我想知道这是如何工作的。

行为说明如下：

这是我为上下文实现的实际代码：

我试图了解如何将列表转换为最小堆。我做了我自己的简单递归实现，这似乎可行，但我很想了解它是如何heapq.heapify工作的。将数组表示为堆，策略是确保在所有不是叶子的索引处都满足堆不变量。这证明了实施的第一部分：

所以我们希望这_siftup(x, i)应该确保在 index 处满足堆不变量i。

这似乎首先向上移动我们开始的任何节点的最小子节点，直到节点的值是叶子（_siftup）。然后它向下移动这个叶子的父节点以找到叶子在堆中的值的正确位置（_siftdown）。为什么这比下面的天真的递归实现更“有效”？图书馆heapq提到了这种情况，但没有解释原因。

我不明白如何正确使用 heapq 模块。

我意识到，如果不将我的列表转换为堆（不使用 heapify），我仍然可以使用其他需要堆作为输入的函数（heappop、heappush..）。那么什么时候需要使用heapify呢？

我应该创建一个空列表，使用 heapify 将其转换为堆，然后使用它吗？我试过这个。我得到了类型错误。

在下面的示例中，如果我不将列表转换为堆，我可以使用 heappush 将 -8 推送到我的列表。但是，当我想查看堆的最小元素时，它给了我 0。在 heapq 文档中，它说我可以使用索引 0 到达最小元素。

我正在尝试在循环中使用它，所以我希望能够执行快速推送和弹出操作，而无需在每次迭代中将列表转换为堆，这将需要 O(N)

因此，我看到了各种帖子，其中用户在尝试从常规列表中进行堆放时会得到“不寻常/意外”的结果。(ex: Unusual result from heappop? ) 解决办法当然是先堆化它。

然而，对于这个LeetCode 解决方案， heapq 方法用于一个常规列表，该列表在使用这些方法之前没有被堆化，但仍然返回正确的预期结果。这是因为当您在常规列表中使用 heappop/heappush 时，它只会弹出/添加列表中的第一个元素？

正如标题所示，我正在尝试使用 Heapq 应用 dijkstra 算法（在 python 中的 dijksta 上的 bogotobogo.com 之后稍作修改 - 长链接；无法输入），我得到 TypeError: 'generator' object is not可在 heapified 列表上使用 heapq.heappop 的结果进行下标（在下面的代码中，我使用 print('the problem is in the line above ...') 来定位错误），我试图避免出现生成器将首先生成（如在列表理解中使用元组 - https://stackoverflow.com/a/56723524/7765766）但没有运气。任何帮助都会受到赞赏，因为这里的移动范围很窄。

我有一个以这种格式存储的列表：[(int, (int, int)), ...]

对于第一种情况，我的代码看起来像这样。

现在我理想的实现是

第二种实现会导致我的代码的其他部分出现问题。是否有任何原因第二个不正确，我该如何纠正它以像 heapq 一样工作

编辑：我知道 heappop() 弹出最小值，这就是为什么我根据“a”对列表进行排序（我假设 heappop 也使用它）

我试图在这里找到代码的时间复杂度。我对 heapq.heappop 的时间复杂度感到困惑，因为每次弹出元素时它都需要维护堆属性。