python - heapq python - 如何修改堆排序的值

Question

我将一个名为 UNVISITED 的空列表转换为一个堆，这样:

UNVISITED = []
heapq.heappush(UNVISITED, (a.f, a))

我推送的对象a，是从一个类中实例化出来的，有以下字段:

class UNVISITEDNode():
    def __init__(self, value1, value2 , value3, value4, value5):
            self.q = value1
            self.h = value2
            self.g = value3
            self.f = value4
            self.p = value5

在我的整个算法中，只要需要，我就会不断修改堆中已有对象的任何 valueX，例如:

for i in range(len(UNVISITED)):
        UNVISITED[i][1].q = newvalue1
        UNVISITED[i][1].h = newvalue2
        UNVISITED[i][1].g = newvalue3
        UNVISITED[i][1].f = newvalue4
        UNVISITED[i][1].p = newvalue5

因为(大概我是这么认为的，如有错误请指正)像我现在这样修改值f不会改变影响堆排序的值，我直接试试修改 UNVISITED[i][0](上面的 a.f 在创建堆时作为第二个参数的第二部分传递)。

[问题] -> 然后我被告知这个值不允许修改:

UNVISITED[i][0] = newvalue4

*Traceback (most recent call last):
  File "/home/daniel/pycharm-2017.3.3/helpers/pydev/
_pydevd_bundle/pydevd_exec.py", line 3, in Exec
        exec exp in global_vars, local_vars
      File "<input>", line 1, in <module>
    TypeError: 'tuple' object does not support item assignment

我真的需要修改对象a的值f，每次都需要影响堆的排序，你不能这样做这通过UNVISITED[i][1].f = newvalue4(显然)。有什么办法可以做到这一点或解决方法吗？

编辑(已执行解决方法)

最终我定义了一个简单的手动堆作为 heap = [] 和 heap.append() 对象。您可以使用 heap.pop() 弹出堆中的第一个元素，并使用 heap.sort(key=lambda x: x.f, reverse=True) 对其进行排序基于属性的值。像这样，您可以更接近 heapq 的行为，并且可以修改堆中为其排序的元素。重要的是要说这比使用 heapq 慢得多。

尽管如此，由于其他可能解决方法的详细信息，我将@Raymong Hettinger 的回答标记为好的回答。

此外，@Davis Yoshida 提出了一个有效的观点，即定义的堆可能不是存储数据的最佳方式。

Answer 1

无效并重新插入

通常的解决方案是将对象标记为无效并重新插入一个新值。弹出值时，只需忽略无效条目。

只要不存在大量无效条目，这种技术就非常有效。失效步骤在 constant time 中运行随后的流行音乐在 logarithmic time 中运行.

重新堆积

调整一个或多个值后，运行 heapify()恢复堆不变量的函数。

这使用保证在 linear time 中运行的公共(public)函数.

直接堆调整

另一种方法是使用list.index() 在堆列表中定位对象。 .更改值后，根据值是增加还是减少运行内部 _siftup() 或 _siftdown() 函数。

增加大小写:

>>> from heapq import _siftup, _siftdown, heapify, heappop

>>> data = [10, 5, 18, 2, 37, 3, 8, 7, 19, 1]
>>> heapify(data)
>>> old, new = 8, 22              # increase the 8 to 22
>>> i = data.index(old)
>>> data[i] = new
>>> _siftup(data, i)
>>> [heappop(data) for i in range(len(data))]
[1, 2, 3, 5, 7, 10, 18, 19, 22, 37]

递减大小写:

>>> data = [10, 5, 18, 2, 37, 3, 8, 7, 19, 1]
>>> heapify(data)
>>> old, new = 8, 4              # decrease the 8 to 4
>>> i = data.index(old)
>>> data[i] = new
>>> _siftdown(data, 0, i)
>>> [heappop(data) for i in range(len(data))]
[1, 2, 3, 4, 5, 7, 10, 18, 19, 37]

此技术使用线性时间列表索引和 logarithmic time堆更新。它可能比重新堆化技术使用更少的比较，但这并不完全令人满意，因为它使用非公共(public)函数。

度假村

最后，您可以对数据进行求值:

>>> data.sort()

这种技术可能比重新堆化或直接堆调整进行更多的比较。它起作用的原因是“如果数据已排序，那么它已经是一个堆”。

运行时间在最坏情况下可以是O(n log n)；然而，排序 实现适用 Timsort对部分排序的输入非常有效的算法。