支持修改元素的堆？
这是我的情况。我想在Python中实现A*算法，但不想使用线性时间的最小值或插入操作。我需要一个堆来高效地获取权重最低的项目。
我最初的想法是“太简单了！我用heapq就行！”但后来我发现，生活往往没有我们想象的那么简单。结果发现，这个方法在A*算法的一个关键点上并不理想。当考虑到子节点时，我需要偶尔更新已经在堆里的子节点的分数。
对于那些对A*算法记忆有些模糊的人来说，简单来说，我想要取出一个元素，修改它的权重，并且在堆中反映这个变化，所有这些操作都要在亚线性时间内完成。
有没有什么建议？
3 个回答
我总是自己实现一个堆（Heap）类型，原因很简单：在堆里你无法直接搜索，而所有高效的方法都需要“指向元素的指针”作为输入。
通常，我会把我的堆实现成一个无结构的物品容器和一个指向这些物品的指针（或索引）的堆的组合。如果你在物品里保存一个指向堆位置的指针，就能形成一个双向链接： a) 给定一个堆元素（比如通过extractMin返回的，或者在比较时得到的）：解引用这个指针，你就能得到你的物品。 b) 给定一个物品（比如通过图算法的邻接表）：把指针传递给你想要的任何更新函数。
当然，这样会增加一些空间开销（每个物品多了两个指针或整数），但这让堆的重构变得非常便宜（只需交换几个指针，而不是整个物品），这也让你在物品中添加一些额外的数据变得不那么麻烦。
确实，heapq里的堆函数和Queue.PriorityQueue都不是特别好用。你要么花时间在博客上发牢骚，要么自己动手实现一个，差不多都需要一样的时间。
从复杂度的角度来看，你可以尝试使用二项堆或斐波那契堆；在Python中似乎都有这两种堆的实现，但没有成熟的库可以直接用。不过，二叉堆或d-叉堆在实际使用中可能会更快一些。heapq页面上提到如何进行更新（保持对你插入堆中的项目的引用，标记为无效，然后插入一个新版本）。不过，更新后保持堆的性质还有更快的算法。你可以查看http://en.wikipedia.org/wiki/D-ary_heap，了解快速更新所需的算法，但你可能需要在数组上自己实现一个堆才能使用这些算法。