适合双端排序列表的最佳数据结构

Question

我需要一个数据结构，能够做到以下几点：

• 可以排序
• 让我能快速从列表的前面和后面取出值，时间复杂度是 O(log n)
• 在我插入新值后，依然保持排序状态
• 允许用户指定比较函数，因为我会存储元组，并希望根据特定的值进行排序
• 不需要考虑线程安全
• 可选地支持高效的 haskey() 查找（不过我也可以单独维护一个哈希表来处理这个）

目前我在想，我可能需要一个优先队列和一个哈希表，虽然我不确定能否在优先队列的两端都快速取出值。另一个选择是维护一个有序字典，每次添加数据时都进行插入排序。

因为我对性能有一定要求，数据量大概在 20 万以下，所以我不太确定这些操作需要什么样的渐进性能。n 不会无限增长，所以在 k * O(n) 中，低常数性能 k 可能和 O(n) 一样重要。也就是说，我希望插入和取出的操作都能在 O(log n) 的时间内完成。

另外，Python 中有没有特别的实现？我真的不想自己写这段代码。

Answer 1

我建议使用一种平衡的二叉树，比如红黑树。

在PyPi上搜索一下，可以找到几个相关的实现。用谷歌搜索也能找到更多信息。

在PyPi上，bintrees看起来非常完整，支持Python和C/Cython的实现。不过我没有使用过，所以要小心哦。

红黑树是一种保持有序的数据结构，大多数操作（比如插入、删除、查找）的时间复杂度是O(log2(N))，这意味着在一个有20万个条目的树中，平均查找一个元素大约需要17到18次比较。

Answer 2

除了哈希的部分，你需要的是一个双端优先队列，也叫优先双端队列。

如果你只需要管理数据的最小值和最大值，可能还可以考虑一种叫做区间堆的数据结构。它的好处是可以在 O(1) 的时间内查看最小值和最大值（也就是很快就能知道这两个值），不过删除最小值和最大值的操作还是需要 O(log(N)) 的时间。可惜的是，我不知道在 Python 中有没有现成的实现，所以你可能需要自己写一个。

如果你对区间堆感兴趣，这里有一本算法教材的附录，里面详细介绍了区间堆：

http://www.mhhe.com/engcs/compsci/sahni/enrich/c9/interval.pdf

Answer 3

对于这类操作，你可以使用 blist 或者数据库（比如标准库里有的 sqlite）来获得不错的性能。