Name of datastructure  | 
                Pypi link  | 
                Implementation language  | 
                Origin  | 
                Sort time  | 
                find_min time  | 
                find_max time  | 
                Does well with ordered keys?  | 
                Storage overhead beyond binary tree?  | 
                Notes  | 
            
| Treap | pypi | Python2/Python3 and/or Cython (m4) | Ported from Java by me | O(n) | O(log2(n)) | O(log2(n)) | Yes | One machine word per element stored. | |
| Red-Black Tree | pypi | Python2/Python3 | Mostly Duncan G. Smith, but me too | O(n) | O(log2(n)) | O(log2(n)) | Yes | One machine word per element stored. | Supports both dict-like and set-like use | 
| Splay Tree | pypi | Python2/Python3 | Originally from here, but I've added considerable polish. | O(n) | O(log2(n)) | O(log2(n)) | No | None | Storing or retrieving all keys in order would reduce it to a linked list. Recently-accessed keys are kept near the root of the tree: good for caches | 
| Scapegoat Tree | pypi | Python2/Python3 | Originally from here. | O(n) | O(log2(n)) | O(log2(n)) | Kind of | None | This datastructure reorganizes itself (within limits) to improve search times / storage times with no bookkeeping storage overhead. | 
| Binary Search Tree | pypi | Python2/Python3 | Originally from here. | O(n) | O(log2(n)) | O(log2(n)) | No | None | Storing all keys in order will reduce this to a linked list | 
Name of datastructure  | 
                Pypi link  | 
                Implementation language  | 
                Origin  | 
                Notes  | 
            
| Bloom Filter | pypi | Python2/Python3 | This recipe plus some original work by me | Probabilistic set datastructure that never gives a false negative, but gives false positives with a user-adjustable probability | 
| Hash Table | N/A | C | Original work by me | Includes one version that works for all types using void *, and another that autogenerates one instance of the code for each type. | 
| Linked List | pypi | Python2/Python3 | Original work by me | Singly-linked list. Includes Stack and Queue implementations | 
| Dupdict | pypi | Python2/Python3 | Original work by me | Builds on an arbitrary dictionary(-like) type to allow duplicates | 
| fibonacci-heap-mod | pypi | Python2/Python3 | Ported from Java by me | A priority queue with nice theoretical limits | 
| bits_mod | pypi | Python2/Python3 | Original work by me | A bit array that can adapt to different long sizes | 
| trie_mod | pypi | Python2/Python3 | B. Dimmick's trie implementation | A Trie: Constant time lookup of potentially-many strings; one node for each character in a hierarchy of characters. These are nice for storing natural language dictionaries and similar data | 
You can e-mail the author with questions or comments: