python是否有排序列表? [英] Does python have a sorted list?

问题描述

我的意思是具有以下结构:

By which I mean a structure with:

操作的
• O(log n)复杂度
• O(log n)查找元素的复杂度
• O(n)复杂度来计算要排序的list(x)

我也有一个关于list(...).insert(...)性能的问题，现在此处.

I also had a related question about performance of list(...).insert(...) which is now here.

推荐答案

标准Python列表未以任何形式排序.标准的 heapq 模块可用于将O(log n)附加到现有列表，并删除O(log n)中最小的列表，但在定义中不是排序列表.

The standard Python list is not sorted in any form. The standard heapq module can be used to append in O(log n) to an existing list and remove the smallest one in O(log n), but isn't a sorted list in your definition.

有多种符合您要求的Python平衡树实现，例如 rbtree ， RBTree 或 pyavl .

There are various implementations of balanced trees for Python that meet your requirements, e.g. rbtree, RBTree, or pyavl.

这篇关于python是否有排序列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！