这是我的场景。我想实现A *（使用Python），而不必求助于线性时间min或操作。我需要一堆能够有效地获得最低重量的物品。支持修改元素的堆？
我的直接回复是'Easy！我会用heapq！'然后我发现生活并不像我们希望的那样简单。事实证明，这种策略对于A *的关键点之一来说并不理想。当考虑到孩子时，我需要偶尔更新已经在堆上的孩子的分数。
对于那些记忆A *已经失效的人来说，它的要点是我想要一个元素，修改它的权重，并修改堆来反映变化，所有这些都在次线性时间。
有什么建议吗？
出于复杂性的考虑，你会想尝试一个二项式或Fibonacci堆;似乎在Python中有两个实现，但不是生产级库。尽管如此，二进制或d-ary堆可能在实践中工作得更快。 heapq页面提到了如何进行更新（保留对插入到堆中的项目的引用，将其标记为无效，然后插入新版本）。尽管如此，在更新后维护堆属性的算法更快。查看http://en.wikipedia.org/wiki/D-ary_heap以了解用于快速更新的算法，但您可能需要在这些数组的顶部实现自己的堆。
确实，heapq和Queue.PriorityQueue中的堆函数都没有任何功能。它可能需要大致相同的时间来A：在你的博客上写一个咆哮或B：你自己实现一个。
我总是最终实现自己的Heap类型版本，确切的原因是您实际上无法在Heap中进行搜索，而所有有效的方法都需要“指向元素的指针”作为输入。
通常，我将Heap实现为Items的非结构化容器和指向项的指针（或indeces）的堆的组合。如果在项目中保留一个指向Heap位置的指针，则有一个直接的双向链接： a）给定Heap元素（例如，由extractMin返回，或者在比较过程中）：取消引用指针，并且获得你的物品。 b）给定一个项目（例如通过Graph算法的邻接列表）：将指针传递给你想要的任何更新函数。当然，这会导致空间开销（每个Item有2个额外的指针/整数），但它使堆重构非常便宜（交换几个指针而不是交换整个项），这反过来使添加一些额外的卫星数据到您的项目。