我需要收集的數據結構，可以做到以下幾點：最佳數據結構使用兩結束排序列表
在此階段我的想法是，我需要一個優先級隊列和一個哈希表，雖然我不知道我是否可以快速彈出這兩個端點的優先級隊列值。另一種可能是簡單地維護一個OrderedDictionary並且每次向它添加更多數據時進行插入排序。因爲我對中等數量的項目（我估計少於200,000）的表現感興趣，所以我不確定我需要這些操作的漸進性能。 n不會無限增長，因此k的k的k * O(n)可能與O(n)一樣重要。也就是說，我寧願插入和彈出操作都需要O(log n)時間。
此外，Python中是否有特定的實現？我真的很想避免自己寫這段代碼。
如果這是Java，我會使用帶有NavigableSet接口的TreeSet。
這實現爲紅黑樹。
我建議某種平衡的二叉樹，如紅黑樹。
A search on PyPi拋出了一些實現。在谷歌上搜索會給你更多。
bintrees PyPi看起來非常完整，並且具有Python和C/Cython實現。我沒有使用它，所以要注意空格。
紅黑樹保持排序並且大多數操作（插入，刪除，查找）都是O（log2（N）），因此在一個包含200,000個條目的樹中查找元素將平均進行17-18次比較。
聽起來像skip list將滿足您的所有要求。它基本上是一個動態大小的排序鏈表，帶有O（log n）插入和刪除。
我真的不知道Python，但這種聯繫似乎是相關的：
http://infohost.nmt.edu/tcc/help/lang/python/examples/pyskip/
我想你需要它來分類的，因爲你在排定的順序由排名進入元素？
您可以使用任何平衡二叉樹的任何實現，每個節點的附加信息告訴您該節點的後代數（通常稱爲Order Statistic Binary Tree）。
使用此結構，給定元素的排名（偶數最小/最大），您可以在O（log n）時間訪問/刪除它。
這使得所有的操作（訪問/插入/刪除等級，彈出前/後，插入/刪除/按值搜索）O（logn）時間，同時允許自定義排序方法。
而且，顯然Python有AVL樹（第一平衡樹結構中的一種）的實施，支持順序統計：http://www.python.org/ftp/python/contrib-09-Dec-1999/DataStructures/avl.README
所以，你將不再需要自定義實現。
除了哈希，你要找的是一個雙端優先級隊列，又名優先級隊列。
如果您對排序的需求不超出管理數據的最小值和最大值，那麼您需要查看的另一個結構可能是間隔堆，它具有O（1）查找min和最大值，如果你需要查看值（儘管deleteMin和deleteMax仍然是O（log（N）））。不幸的是，我沒有意識到Python中的任何實現，所以我認爲你不得不推出自己的。
這裏是一個增編描述區間堆，如果你有興趣的算法教材：
http://www.mhhe.com/engcs/compsci/sahni/enrich/c9/interval.pdf
如果你真的可以讓O（log n）的流行樂，出隊，並插入，然後像紅黑樹這樣的簡單均衡搜索樹就足夠了。當你（1）向樹中插入元素或者（2）彈出或者退出時，你可以優化這個，當然這是通過維護一個直接指向樹中最小和最大元素的指針，然後更新它使resp無效。指針。但是因爲樹是平衡的，無論如何都有一些洗牌，你可以更新相應的內容。指針在同一時間。
還有一些叫做min-max heap的地方（見二維堆的維基百科條目），它實際上實現了一個「雙端優先級隊列」，即可以從前端和後端都彈出的隊列。但是，您無法按順序訪問整個對象列表，而搜索樹可以在O（n）時間內有效地迭代。
然而，min-max堆的好處是可以在O（1）時間內讀取最小和最大對象，搜索樹只需要O（log（n））來讀取min或max最大對象，除非你有緩存的指針，如上所述。
這聽起來像一個最小最大堆，加上一個哈希表，就是我想要的。 – fmark 2010-05-20 02:20:15
min-max堆很酷！我實際上不知道他們存在之前，我發現他們在更早的stackoverflow :) – 2010-05-21 15:40:36
我假設「快速流行」的意思是最多O（log n）。但是，您需要多快才能插入新值？上）？ O（log n）？ O（1）？ – kennytm 2010-05-15 06:21:54
感謝KennyTM澄清了這個問題。 – fmark 2010-05-15 06:25:38