python - 支持修改其元素的堆？

Question

这是我的场景。我想实现 A*（在 Python 中），而不必求助于线性时间最小值或操作。我需要一个堆才能有效地获得重量最低的物品。

我的第一反应是‘简单！我将使用 heapq！然后我发现生活很少像我们希望的那样简单。事实证明，这种策略对于 A* 的关键点之一不是最优的。当考虑孩子时，我需要偶尔更新已经在堆上的孩子的分数。

对于那些对 A* 的记忆有一点点流失的人来说，它的要点是我想取一个元素，修改它的权重，并修改堆以反映变化，所有这些都在亚线性时间内完成。

有什么建议么？

Answer 1

出于复杂性目的，您可能想尝试二项式或斐波那契堆；似乎在 Python 中都有实现，但没有生产级库。不过，二进制或 d-ary 堆在实践中可能工作得更快。该heapq页面提到了如何进行更新（保留对您插入堆中的项目的引用，将其标记为无效，然后插入新版本）。不过，有更快的算法可以在更新后维护堆属性。查看http://en.wikipedia.org/wiki/D-ary_heap以了解用于快速更新的算法，但您可能需要在数组顶部实现自己的堆。

Answer 2

我总是最终实现我自己的堆类型版本，确切的原因是你实际上不能在堆中搜索，而所有有效的方法都需要“指向元素的指针”作为输入。

通常，我将我的堆实现为项目的非结构化容器和指向项目的指针（或索引）堆的组合。如果你在 Item 中保留一个指向 Heap 位置的指针，你就有一个直接的双向链接：a) 给定一个 Heap 元素（例如由 extractMin 返回，或在比较期间）：取消引用指针，你就得到了你的物品。b) 给定一个项目（例如通过图形算法的邻接列表）：将指针传递给您想要的任何更新函数。

当然，这会导致空间开销（每个项目 2 个额外的指针/整数），但它使堆重组非常便宜（交换几个指针而不是交换整个项目），这反过来减少了添加一些额外的卫星数据到你的物品。

Answer 3

确实，堆中的功能heapq都不Queue.PriorityQueue是很实用。A：在您的博客上写一篇咆哮或 B：自己实现一个可能需要大约相同的时间。