Best data-structure to use for two ended sorted list

Posted by fmark on Stack Overflow See other posts from Stack Overflow or by fmark
Published on 2010-05-15T06:18:28Z Indexed on 2010/05/15 6:24 UTC
Read the original article Hit count: 299

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.

© Stack Overflow or respective owner

Related posts about python

Related posts about data-structures