我有一个 python 程序，我在其中使用优先级队列来跟踪要处理的对象。目前，队列是使用 SortedList 实现的，效果很好。
但是，我需要扩展这段代码，以便列表保持按多个键排序。有点像在多列上有索引的 SQL 数据库，这样我就可以高效地访问、添加和删除所有键上的对象。我的工作量添加/删除繁重。为了让您了解我想做什么，这里有一些伪代码:
ml = MultiSortedList()
ml.append((1, "z", 1.5), a)
ml.append((2, "a", 40.0), b)
ml.append((3, "f", 0.5), c)
print(ml.sorted(0))
[((1, "z", 1.5), a),
((2, "a", 40.0), b),
((3, "f", 0.5), c),]
print(ml.sorted(2))
[((3, "f", 0.5), c),
((1, "z", 1.5), a),
((2, "a", 40.0), b)]
print(ml.sorted(2).pop(1)
(1, "z", 1.5), a)
print(ml.sorted(0))
[((2, "a", 40.0), b),
((3, "f", 0.5), c)]
我不太明白如何有效地做到这一点。当然，我可以为每次访问不同的列再次对列表进行排序，但这太昂贵了。此外，Python 列表的 O(n) 删除操作变得很痛苦，因为列表可能包含数千个对象。
是否有解决此问题的现有数据结构(最好已经在 python 中实现)？如果没有，你能帮我制定一个如何有效实现的大纲吗？
最佳答案
您应该使用 heap 而不是使用排序列表作为优先级队列的实现。 .例如，二进制堆有 log(n) 插入和删除。 Fibonacci 堆将有 O(1) 插入。
您在标准库中有一个实现:heapq模块。
对于您的用例，您需要保留多个堆:一个用于每个排序顺序。为了实现的清晰度，您可能希望将原始数据保存在字典中(可能使用随机或递增键)并且只将其键保存在堆上。
使用这种技术，您可以轻松地实现O(1) 插入和O(log(n)) 删除。你并没有真正指定你将拥有什么样的访问权限，但如果你需要随机访问，你可以使用 binary search在适当的堆上得到 O(log(n))
关于python - 保持对象按多个键排序的高效数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29118602/