问题标签 [heapq]

在文档中，它提到它可能是元组。但它可以是列表吗？如果是，那么优先级是否默认由列表的第一个元素决定？因为在文档中的 Priority Queue Implementation Notes 中，他们已经用 list 来说明了吗？

我有一个数组arr = [1,2,1,3]。

当我使用heappush函数将数组元素按原样推送到堆中时，其顺序与数组中的顺序完全相同：

现在，如果我推送arr元素的负值，堆就会按预期排序。

我想知道为什么当它们的负值被添加到堆中时heappush对数组元素进行排序但是当正值被推入堆时它不做任何事情。

以官方heapq为例：

我想进一步实现一个有效的selective_push，这样

1. selected_push((1, 'M')) 等价于 heappush，因为 'M' 不在堆中
2. selected_push((3.5, 'N')) 等价于 heap[2]= (3.5, 'N'); heapify(heap) 自 3.5<4
3. 从 4.5>4 开始，selective_push((4.5, 'N')) 什么都不做

以下实现解释了目标，但速度很慢：

我认为由于线性搜索，它很慢，它破坏了 .log(n) 的复杂性heapq.push。替换率低，但总是执行线性搜索。

在 Python 3 中，我像这样使用 heapq：

有没有办法迭代 heapq 以便我按排序顺序获取值而不改变 heapq/丢失数据？

如果没有，我怎样才能有效地模仿所需的行为？

我想出的解决方案是创建一个临时堆，当我从原始堆弹出时推送到它，一旦我完成迭代，将原始堆设置为等于临时堆。

当然这不是很有效，并且改变了原始堆引用的对象。

我想知道为什么 python 中的 heapq 在使用 heappush 时不按词法顺序对字符串进行排序？下面是我试过的代码。有人知道他们为什么打印不同的订单吗？

我在leetcode.com上查看这个问题的解决方案

当我为它提供一个字符串数组时["aa", "aaa", "a"]，1 它会正确返回["a"]. 我的问题是堆是否也在内部按字典顺序对元组进行排序？因为根据我的说法，如果没有排序，它会简单地返回["aa"]（构建堆的顺序，因为所有三个的计数都是相同的）。还是我误解了heapq？

我正在尝试在 Python 中开发一个 15 星拼图程序，它应该使用星搜索算法按数字顺序对所有内容进行排序，0 位于末尾。

这是我迄今为止开发的明星算法：

这是我的程序的其余部分。假设在以下情况下一切正常：

我已经设法在我的 best_first_graph_search_manhattan 函数中将其缩小到我的 for 循环中，如果 if 语句检查子项是否未在探索中且子项不在边界中，则似乎会导致无限循环。我不确定是我调用子函数的方式还是我将边界和子函数推入我的优先级队列的方式。我已经将 heapq 导入到我的程序中，并且我已经进行了广泛的研究，其中导入该函数可以让您在程序中使用优先级队列。请不要介意我的星搜索中未使用的其他变量。

这是一个测试用例：1 0 3 4 5 2 6 8 9 10 7 11 13 14 15 12 | DRDRD

非常感谢大家的帮助！

所以在 Python 中，当我输入

它给

不是'自己的工具狗'>'艺术零'吗？为什么heapq中的元组比较在这里不起作用？

来自https://www.tutorialspoint.com/heap-queue-or-heapq-in-python：

heappush - 这个函数在不改变当前堆的情况下向堆中添加一个元素。

如果当前堆没有改变，我们为什么不使用append()列表方法呢？新元素的列表是否仅在heappop()被调用时才被堆积？

我是否误解了“不改变当前堆”？或者是其他东西？

在下面的代码中，heapq.heappop()不检查列表是否已堆积。那为什么会存在这个方法呢？会不会h.pop(0)等价？