支持修改其元素的堆？

Question

这是我的设想。我想实现一个*（在Python中），而不必在操作中使用线性时间min。我需要一堆能够有效地得到最低重量的项目。在

我的第一反应是“轻松！我要用heapq后来我发现生活很少像我们希望的那样简单。结果表明，这种策略对于A*的关键点之一是次优的。当考虑孩子时，我需要偶尔更新已经在堆上的孩子的分数。在

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

有什么建议吗？在

Answer 1

出于复杂性的考虑，您可以尝试使用二项式或Fibonacci堆；在Python中似乎有这两者的实现，但没有产品级库。不过，实际上，二进制或d元堆的工作速度可能更快。heapq页面提到了如何进行更新（保留对插入到堆中的项的引用，将其标记为无效，然后插入新版本）。不过，在更新后有更快的算法来维护堆属性。请看http://en.wikipedia.org/wiki/D-ary_heap以了解用于快速更新的算法，但您可能需要在数组的顶部实现自己的堆。在

Answer 2

确实，heapq和Queue.PriorityQueue中的堆函数都不是很好的函数。A:在你的博客上写一篇长篇大论，或者B:你自己实现一个，可能需要同样的时间。在

Answer 3

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

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

当然，这会造成空间开销（每个项目2个额外的指针/整数），但这使得堆重组非常便宜（交换一些指针而不是交换整个项目），这反过来也会使向项目添加一些额外的卫星数据变得不那么痛苦。在