Python中满足指定时间复杂度的高效有序列表实现咨询

你要找的这类数据结构是双端优先队列（Double-ended Priority Queue, 简称DEPQ），完全匹配你提出的有序列表、两端快速弹出最值的需求。

先澄清两个容易混淆的复杂度细节：

• 你提到的弹出操作O(1)，实际指的是可以直接定位到全局最小/最大元素、不需要遍历整个结构的特性。毕竟删除最值后必须调整结构才能保证下一次能快速拿到新的最值，这一步调整的固有成本是O(log n)，所有这类结构的弹出操作均摊复杂度实际为O(log n)，但定位待弹出最值的步骤确实是严格O(1)，和你的需求描述对齐。
• 你标注的插入复杂度要求>= O(log n)大概率是笔误：有序结构插入的理论复杂度下界就是O(log n)，实际场景下大家追求的是插入复杂度不高于O(log n)，下文提到的实现都能达到这个最优效率。

常见的DEPQ底层实现包括最小-最大堆、对称堆、平衡二叉搜索树、跳表等，都符合上述复杂度特征。

Python生态可用实现 #

Python标准库没有提供开箱即用的DEPQ结构，但是有成熟的方案可以直接用：

1. 第三方库sortedcontainers的SortedList #

这是目前Python生态最常用的高性能有序列表实现，纯Python编写无C扩展依赖，安装后即可导入使用。它内部基于分块跳表实现，完全满足你的使用需求：

• 取最小元素：sl[0]，时间复杂度O(1)
• 取最大元素：sl[-1]，时间复杂度O(1)
• 弹出最小元素：sl.pop(0)，均摊时间复杂度O(log n)
• 弹出最大元素：sl.pop()（默认弹出末尾元素），均摊时间复杂度O(log n)
• 插入元素：sl.add(value)，时间复杂度O(log n)

基础使用示例：

from sortedcontainers import SortedList
# 初始化时可以直接传入无序可迭代对象，自动维护有序
sl = SortedList([3,1,4,1,5,9,2,6])
print(sl[0])  # 输出1，直接获取最小值
print(sl[-1]) # 输出9，直接获取最大值
sl.pop(0)     # 弹出头部最小值1
sl.pop()      # 弹出尾部最大值9
sl.add(7)     # 插入新元素，自动调整结构保持有序

2. 基于标准库heapq手动实现 #

如果你不想引入第三方依赖，可以用Python标准库自带的heapq（最小堆实现）自行搭建双端优先队列：维护一个最小堆、一个存储负值的最大堆，再加一个字典做延迟删除标记，也能达到同等复杂度，只是需要自行处理堆中残留的无效过期元素，代码量稍大，适合对依赖引入有严格限制的场景。

注意：不要尝试用普通list或者collections.deque实现这个需求，这两个结构如果要维护元素有序，插入操作的时间复杂度是O(n)，数据量上来之后性能会急剧下降。

内容的提问来源于stack exchange，提问作者student1868