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

Question

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

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

我推送的对象 a 是从 class 实例化而来的，它具有以下字段：

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 提出了一个有效的观点，即定义的 heap 可能不是存储数据的最佳方式。

Answer 1

即使此代码运行，我相信它也不会达到您的预期。具体来说，如果你这样做了

tup = (a.f, a) # a.f = 7

然后可以执行

tup[0] = 3

您可以将 tup 设置为 (3, a)，但 a.f 仍然是 7。

您可以做的一件事是通过向 UNVISITEDNode class 添加 __lt__（小于）方法来允许直接比较，如下所示：

class UNVISITEDNode:
   ...
   def __lt__(self, other):
       return self.f < other.f

然后，不把元组放入heapq，直接把节点对象放入。

但是，如果您修改的对象不在堆的根目录中，您将无法再保证运行堆有效，因此您需要重新堆UNVISITED。

Answer 2

无效并重新插入

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

只要不存在大量无效条目，此技术就非常有效。 constant time and the subsequent pops run in logarithmic time.

中的失效步骤运行s

再堆

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

这使用 public 函数保证 linear time 中的运行。

直接堆调整

另一种方法是使用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()

这种技术可能比重新堆化或直接堆调整进行更多的比较。它起作用的原因是 "if the data is sorted, then it is already a heap".

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

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

heapq python - how to modify values for which heap is sorted

python

sorting

heap

编辑（已执行解决方法）

无效并重新插入

再堆

直接堆调整

度假村