保持可变元素的排序列表是最新的

Question

我可以在 python 中使用 sorted 或 list.sort 来对之前未排序的列表进行排序。

如果我希望我的列表在添加元素时保持排序，我可以使用 sortedcontainers 模块中的 SortedList。

但是，我发现没有现成的方法来保持这个列表随着元素在其中的变化而排序。

from sortedcontainers import SortedList

a = SortedList([], key=len) # sort elements by their length.
a.add([3,3,3]) # add in..
a.add([1]) # .. random..
a.add([2,2]) # .. order.
print(a) # [[1], [2, 2], [3, 3, 3]] still sorted, okay.

# Now, mutate one element.
a[0].append(1)
a[0].append(1)
print(a) # [[1, 1, 1], [2, 2], [3, 3, 3]] not sorted, not okay.

我了解 SortedList 不负责跟踪其中包含的项目的更改并保持排序最新。

那么如何更新排序？
有没有我可以发送到 a 的消息，以便它知道我在索引 0 处进行了更改，它会重新考虑项目 0 的位置，例如 a.update_sorting_of(0)。
是否有另一种数据结构专门用于此？
我应该自己写优化吗？
我应该解决它并改为 a.add(a.pop(0)) 吗？
与专用解决方案相比，此解决方法如何？

我可以放心地假设 a[0] 在我的案例中没有触发其他元素的任何变化（否则我只会 a.sort(key=len) 整个事情）。

Answer 1

没有机制可以做你想做的事。即使你在改变一个元素之后求助于一个列表，它也会有 O(nlogn) 的复杂性。但是因为 add() 在幕后使用了二分法，所以它只有 O(logn)。所以最好像你建议的那样做，即删除要突变的元素并重新添加它。如果有一个函数可以满足您的要求，它可能会在幕后执行类似的操作，因为我想不出比 bisect 更好的方法来放置排序顺序可能已更改的元素。

def mutate_element(sortedlist, index, value):
    temp = sortedlist.pop(index)
    temp.append(value)
    sortedlist.add(temp)

您还可以进一步概括各种列表变异方法的功能。例如 getattr(mylist, 'append') 与 mylist.append 相同。

保持可变元素的排序列表是最新的

Keep sorted list of mutable elements up to date

python

python-3.x

list

sorting

mutable