quicksort和heapsort都进行就地排序.哪个更好？什么是首选的应用程序和案例？
我有一个python程序,我使用优先级队列来跟踪要处理的对象.目前,队列是使用SortedList实现的,而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)]
我无法弄清楚如何有效地做到这一点.当然,我可以再次为每个访问不同列的列表排序,但这太贵了.此外,O(n)python列表上的删除操作变得很痛苦,因为列表可能包含数千个对象.
是否有现有的数据结构(最好已经在python中实现)来解决这个问题？如果没有,你能帮我概述一下如何有效地实现这个目标吗？