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

问题描述

我的意思是一个结构:

• x.push() 操作的复杂度为 O(log n)
• O(log n) 查找元素的复杂度
• O(n) 计算将被排序的 list(x) 的复杂度

• O(log n) complexity for x.push() operations
• O(log n) complexity to find an element
• O(n) complexity to compute list(x) which will be sorted

我也有一个关于 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屋！