Best data-structure to use for two ended sorted list
- by fmark
I need a collection data-structure that can do the following:
Be sorted
Allow me to quickly pop values off the front and back of the list
Remain sorted after I insert a new value
Allow a user-specified comparison function, as I will be storing tuples and want to sort on a particular value
Thread-safety is not required
Optionally allow efficient haskey() lookups (I'm happy to maintain a separate hash-table for this though)
My thoughts at this stage are that I need a priority queue and a hash table, although I don't know if I can quickly pop values off both ends of a priority queue. I'm interested in performance for a moderate number of items (I would estimate less than 200,000). Another possibility is simply maintaining an OrderedDictionary and doing an insertion sort it every-time I add more data to it.
Furthermore, are there any particular implementations in Python. I would really like to avoid writing this code myself.
