On Sat, 14 Mar 2020 20:35:08 -0000 1njection1@gmail.com wrote:
In other languages, there are built-in data structures with binary search tree semantics, as an example, std::map in C++.
By binary search tree semantics we mean the following:
* We can insert elements into the structure in time faster than O(n), i.e. O(logn) for std::map
* We can iterate over all of the elements of the structure in sorted order in linear time, i.e. O(n) for std::map
Is there currently any data structure in Python with binary search tree semantics?
To illustrate the need, can the following program be written elegantly and efficiently with built-in Python data structures?
Imagine that you are a fund manager at a bank. Bank accounts are added to your fund very frequently. A bank account has an ID and a value. A smaller ID means that the bank account was created earlier than one with a larger ID. Each time that an account is added to your fund, you would like to know the ID number of the 1000th oldest account, for your records.
Have you considered Python's heapq module? It fails to meet your second semantic (iterating in linear time), but should work pretty well for your stated use case (finding the 1000th oldest element in a heap). Also, if you're talking about bank accounts, ISTM that the persistent, secure storage mechanisms would swamp the time for finding the 1000th oldest account. Or are all of your account data only stored in memory? Dan -- “Atoms are not things.” – Werner Heisenberg Dan Sommers, http://www.tombstonezero.net/dan