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: