python - 如何在 O(lgn) 中堆积 heapq？

Question

可能重复：
如何在 Python 的 heapq 中实现减少键功能？

你好，

我在 Python 中使用 heapq 来实现优先级队列。队列中的项目的优先级发生了很大变化，当发生这种情况时，我需要堆化 heapq。
问题是 heapq 只有一个 heapify 函数来堆整整个堆，而不是从堆内的某个项目开始的 heapify 知道其余部分已经是一个有序的堆（就像经典的 CS 教科书 heapify）。
差异很大，因为每个 heapify 调用都是 O(n) 而不是 O(lgn)。可以在不使用标准列表实现堆的情况下完成吗？

谢谢！

---

看来我的问题与如何在 Python 的 heapq 中实现减少键功能重复？
那里的答案表明，没有办法使用特定项目的适当 O(lgn) heapify 重新实现基于堆的队列。

Answer 1

我能够通过使当前堆项目无效（在项目内引发标志）并将相同的项目推送到堆（即 O(lgn)）来避免 heapify 的这个特殊问题。
这可能会用一些无效的项目（我在 pop() 处清理）使堆膨胀，但避免使用知道它们当前堆位置的堆项目和基于新位置的 heapify 重新实现堆。