阅读 桌面完整版

有序数据结构在编程中（尤其是算法竞赛和竞技编程）非常实用。在 Python 中，主要由 Sorted Containers 库提供三种有序数据结构：SortedDict、SortedSet 和 SortedList。

深入理解 Python 有序数据结构：从内置到 SortedContainers

Python 有序数据结构完整指南

Python 中的有序列表、字典与集合实战解析

带你玩转 Python SortedContainers 与内置排序结构

Python 开发者必读：SortedContainers 与内置数据结构对比

Python 有序数据结构教程

排序是编程中最常见的操作之一。Python 提供了多种方式来维护有序数据，从内置的列表、集合、堆，到第三方库 sortedcontainers。

本教程将介绍 Python 的有序数据结构，它们的优缺点，以及实际应用场景。

内置选项

1. list + bisect

你可以使用 bisect 模块手动维护一个有序列表。

import bisect

nums = [1, 3, 5]
bisect.insort(nums, 2)  # 插入并保持有序
print(nums)  # [1, 2, 3, 5]

这种方法有效，但插入和删除操作是 O(n)，因为需要移动元素。

2. heapq

heapq 模块实现了优先队列。它部分有序，可以高效获取最小或最大值。

import heapq

nums = [5, 1, 3]
heapq.heapify(nums)   # 转换为堆
print(heapq.heappop(nums))  # 1

适合频繁取最小/最大值，但不会维护全局有序。

3. dict 和 set

字典和集合在 Python 中基于哈希表。它们提供 O(1) 查找，但不保持有序。

myset = {3, 1, 2}
print(2 in myset)   # True
print(sorted(myset))  # [1, 2, 3]

如果需要真正的有序结构，就需要更好的工具。

sortedcontainers 库

sortedcontainers 提供了三个强大的数据结构：

• SortedList
• SortedDict
• SortedSet

它们能自动保持有序，并且插入、删除都是 O(log n)。

安装方式：

pip install sortedcontainers

SortedList

像列表，但始终保持有序。

from sortedcontainers import SortedList

sl = SortedList([5, 1, 3])
print(sl)   # SortedList([1, 3, 5])

sl.add(2)
print(sl)   # SortedList([1, 2, 3, 5])

sl.remove(3)
print(sl)   # SortedList([1, 2, 5])

print(sl.bisect_left(2))   # 1

应用场景：实时统计、滑动窗口中位数、排行榜。

SortedDict

像字典，但键有序。

from sortedcontainers import SortedDict

sd = SortedDict({"b": 2, "a": 1, "c": 3})
print(sd)  # SortedDict({'a': 1, 'b': 2, 'c': 3})

print(sd.peekitem(0))   # ('a', 1)
print(sd.peekitem(-1))  # ('c', 3)

for k in sd:
    print(k, sd[k])

应用场景：有序映射、区间调度、最近邻查询。

SortedSet

像集合，但有序。

from sortedcontainers import SortedSet

ss = SortedSet([3, 1, 2, 2])
print(ss)   # SortedSet([1, 2, 3])

ss.add(5)
print(ss)   # SortedSet([1, 2, 3, 5])

print(ss.bisect_left(3))  # 2

应用场景：去重日志、唯一且有序的数据。

实际应用案例

1. 滑动窗口中位数

from sortedcontainers import SortedList

def sliding_window_median(nums, k):
    sl = SortedList()
    res = []
    for i, num in enumerate(nums):
        sl.add(num)
        if i >= k:
            sl.remove(nums[i-k])
        if i >= k-1:
            if k % 2 == 1:
                res.append(sl[k//2])
            else:
                res.append((sl[k//2-1] + sl[k//2]) / 2)
    return res

print(sliding_window_median([1,3,-1,-3,5,3,6,7], 3))

2. 排行榜系统

from sortedcontainers import SortedList

class Leaderboard:
    def __init__(self):
        self.scores = SortedList()

    def add_score(self, player, score):
        self.scores.add((score, player))

    def top(self, n):
        return self.scores[-n:]

    def reset(self, player, score):
        self.scores.remove((score, player))

lb = Leaderboard()
lb.add_score("Alice", 50)
lb.add_score("Bob", 80)
lb.add_score("Charlie", 70)
print(lb.top(2))

3. 使用 SortedDict 查找最近的键

from sortedcontainers import SortedDict

sd = SortedDict({"a": 1, "c": 3, "e": 5})
idx = sd.bisect_left("d")
print("前驱:", sd.peekitem(idx-1))
print("后继:", sd.peekitem(idx))

何时选择哪种数据结构

– list + bisect: 静态数据，更新少
– heapq: 重复获取最小/最大值
– dict/set: 快速查找但无需排序
– sortedcontainers: 有序且需要频繁更新

总结

sortedcontainers 库为 Python 提供了高效优雅的有序数据结构。如果你需要同时兼顾顺序与性能，它通常比内置工具更合适。

对比表格

特性	list + bisect	heapq	dict	set	sortedcontainers
是否保持有序	是（手动）	否	否	否	是
插入/删除复杂度	O(n)	O(log n)	O(1)	O(1)	O(log n)
随机访问	支持	不支持	仅键	不支持	支持
范围查询	不支持	不支持	不支持	不支持	支持
最佳使用场景	静态查找	优先队列	哈希映射	集合查找	有序集合且需更新

英文：A Complete Guide to Sorted Data Structures in Python

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版