如何在O(lgn)时间内堆化heapq？

Question

可能重复的问题：
我该如何在Python的heapq中实现减少优先级的功能？

你好，

我在用Python的heapq来实现一个优先队列。在这个队列里，里面的项目优先级经常会变，这时候我需要对heapq进行重新整理。
问题是，heapq只有一个可以整理整个堆的函数，而没有一个可以从堆里的某个特定项目开始整理的函数，假设其他部分已经是有序的（就像经典计算机教材里讲的那样）。
这个区别很大，因为每次整理的时间复杂度是O(n)，而不是O(lgn)。
有没有办法在不使用标准列表重新实现堆的情况下做到这一点呢？

谢谢！

---

看起来我的问题和我该如何在Python的heapq中实现减少优先级的功能？是重复的。
那里的回答表明，想要在特定项目上实现O(lgn)的整理，必须重新实现一个基于堆的队列。

Answer 1

我通过一种方法避免了这个特定的问题。具体来说，我在当前的堆项目里设置了一个标记，表示这个项目无效，然后再把一个相同的项目放入堆中（这个操作的时间复杂度是O(lgn)）。
这样做可能会导致堆里有一些无效的项目（我在弹出时会清理这些无效项目），但这样就不需要重新实现一个能知道自己在堆中位置的堆项目，也不需要重新进行基于新位置的堆化操作。