支持修改其元素的堆？
这是我的场景。我想实现 A* （在 Python 中），而不必求助于线性时间 min 或操作。我需要一个堆才能有效地获得重量最低的项目。
我的第一反应是‘简单！我将使用 heapq！后来我发现生活很少像我们想象的那么简单。事实证明，对于 A* 的关键点之一来说，该策略并不是最优的。当考虑孩子时，我需要偶尔更新堆上已有孩子的分数。
对于那些对 A* 的记忆有点衰退的人来说，它的要点是我想要获取一个元素，修改它的权重，并修改堆以反映变化，所有这些都在亚线性时间内完成。
有什么建议吗？
Here is my scenario. I want to implement A* (in Python) without having to resort to linear-time min or in operations. I need a heap to be able to efficiently get the lowest weight item.
My immediate response was 'Easy! I'll use heapq!' Then I discovered that life is rarely as simple as we would like it to be. It turns out that this strategy is suboptimal for one of the crucial points of A*. When consider children, I need to occasionally update the scores of the children already on the heap.
For those whose memory of A* has lapse a little, the gist of it is that I want to take an element, modify its weight, and modify the heap to reflect the change, all in sub-linear time.
Any suggestions?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
出于复杂性的目的，您可能需要尝试二项式堆或斐波那契堆；看来 Python 中都有实现，但没有生产级库。不过，二进制堆或 d 进制堆在实践中可能运行得更快。 heapq 页面提到了如何进行更新（保留对插入堆中的项目的引用，将其标记为无效，然后插入新版本）。不过，有更快的算法可以在更新后维护堆属性。查看 http://en.wikipedia.org/wiki/D-ary_heap用于快速更新的算法，但您可能需要在数组顶部实现自己的堆。
For complexity purposes, you would want to try a binomial or Fibonacci heap; it appears that there are implementations of both in Python but not production-grade libraries. A binary or d-ary heap might work faster in practice, though. The
heapqpage mentions how to do updates (keep a reference to the item that you insert into the heap, mark it as invalid and then insert a new version). There are faster algorithms for maintaining the heap property after updates, though. Look at http://en.wikipedia.org/wiki/D-ary_heap for the algorithms to use for fast updates, but you would probably need to implement your own heap on top of an array for those.确实，
heapq和Queue.PriorityQueue中的堆函数都没有什么功能。 A：在博客上写一篇咆哮或 B：自己实现一个可能需要大约相同的时间。It's true, neither the heap functions in
heapqnorQueue.PriorityQueueare very functional. It probably takes about equal time to either A: write a rant on your blog or B: implement one yourself.我总是最终实现我自己版本的堆类型，确切的原因是您实际上无法在堆中搜索，而所有有效的方法都需要“指向元素的指针”作为输入。
通常，我将堆实现为项目的非结构化容器和指向项目的指针（或索引）堆的组合。如果您在项目中保留指向堆位置的指针，则您将拥有直接的双向链接：
a) 给定一个堆元素（例如，由 extractMin 返回，或在比较期间）：取消引用指针，您就得到了您的项目。
b) 给定一个项目（例如通过图形算法的邻接列表）：将指针传递给您想要的任何更新函数。
当然，这会导致空间开销（每个项目 2 个额外的指针/整数），但它使堆重组非常便宜（交换一些指针而不是交换整个项目），这反过来又使得向其中添加一些额外的卫星数据变得不那么痛苦您的物品。
I always end up implementing my own version of a Heap type, for the exact reason that you can't actually search in a Heap, while all efficient methods require "a pointer to the element" as input.
Usually, I implement my Heap as a combination of an unstructured container of Items, and a Heap of pointers (or indeces) to Items. If you keep a pointer to a Heap location in the Item, you have an immediate two-way link:
a) Given a Heap element (e.g. returned by extractMin, or during a comparison): dereference the pointer, and you've got your item.
b) Given an Item (e.g. through an adjacency list of a Graph algorithm): pass the pointer to whatever update function you want.
Of course, this causes space overhead (2 additional pointers/integers per Item), but it makes Heap restructuring very cheap (swapping a few pointers instead of swapping entire Items), which in return makes it less painful to add some additional satellite data to your Items.