heapq python-如何修改已排序堆的值 [英] heapq python - how to modify values for which heap is sorted

问题描述

我将名为UNVISITED的空列表转换为堆，例如:

I transform an empty list called UNVISITED into a heap, such that:

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

从类实例化的我推送的对象a具有以下字段:

The object a that I push, which is instantiated from a class, has the following fields:

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，例如:

Throughout my algorithm, I keep modifying any valueX from the object already in the heap whenever is needed like:

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.)

Because (or so I think, please correct me if I am wrong) modifying the value f like I am doing now does not change the value that affects the sorting of the heap, I directly try to modify UNVISITED[i][0] (which is the above a.f passed as a second part of the second argument when creating the heap).

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

[THE PROBLEM] -> Then I am told that this value does not admit modification:

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来实现.有什么办法或解决方法?

I really need to modify the value f of the object a, which has to affect the sorting of the heap every time is needed and you cannot do this through UNVISITED[i][1].f = newvalue4 (apparently). Is there any way to do this or any workaround?

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

Eventually I have defined a simple manual heap as heap = []and heap.append() the objects to it. You can use heap.pop() to pop the first element in the heap, and heap.sort(key=lambda x: x.f, reverse=True) to sort it based on the values of the attributes. Like this you get closer to the behavior of heapq and you are able to modify the elements in the heap for which that heap is sorted. It is important to say that this is significantly slower than using heapq.

尽管如此，由于其他可能的解决方法的细节，我将@Raymong Hettinger的答案标记为好答案.

Nonetheless, I am marking @Raymong Hettinger 's answer as the good one because of the detail of other possible workarounds.

此外，@ Davis Yoshida提出了一个正确的观点，即定义的堆可能不是存储数据的最佳方法.

Also, @Davis Yoshida has made a valid point in that maybe a heap as it is defined might not be the best way to store the data.

推荐答案

无效并重新插入

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

Invalidate and Reinsert

The usual solution is to mark the object as invalid and to reinsert a new value. When popping off values, just ignore the invalid entries.

只要没有大量无效的条目，此技术就会非常有效.无效步骤在恒定时间中运行，随后的弹出窗口在

This technique is very efficient as long as there are not a large number of invalidated entries. The invalidation step runs in constant time and the subsequent pops run in logarithmic time.

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

After adjusting one or more values, run the heapify() function to restore the heap invariant.

这使用保证可以在线性时间中运行的公共功能.

This uses a public function that is guaranteed to run in linear time.

另一种方法是使用 list.index() .更改值后，根据是增加还是减小值，运行内部的 _siftup()或 _siftdown()函数.

Another way is to locate the object in the heap's list, using list.index(). After changing the value, run the internal _siftup() or _siftdown() functions depending on whether the value is being increased or decreased.

案件增多:

>>> 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]

此技术使用线性时间列表索引和对数时间堆更新.与重新定义技术相比，它使用的比较可能更少，但这并不完全令人满意，因为它使用了非公共函数.

This technique uses linear time list indexing and a logarithmic time heap update. It is likely to use fewer comparisons than the reheapifying technique, but this isn't entirely satisfying because it uses non-public functions.

最后，您可以使用数据:

Lastly, you can resort the data:

>>> data.sort()

与重新定义堆或直接调整堆相比，此技术可能进行的比较更多.起作用的原因是如果对数据进行排序，那么它已经是堆".

This technique likely makes more comparisons than reheapifying or direct heap adjustment. The reason it works is that "if the data is sorted, then it is already a heap".

在最坏的情况下，运行时间可以为O(n log n)；但是， sort 实现使用 Timsort 算法，该算法对于部分排序的输入非常有效.

The running time can be O(n log n) in the worst case; however, the sort implementation applies the Timsort algorithm which can be very efficient with partially sorted inputs.

这篇关于heapq python-如何修改已排序堆的值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！