Datastructure
Theory

Tree or Heap?

Python Implementations

Notes
Treap Wikipedia Kinda both treap.py Probabilistic, supposed to have good modify at the expense of lookup. Supposed to be faster than a red-black tree, but more variable.
Splay Tree Wikipedia Tree
  • splay_mod
  • pysplay (above entry was derived from this one?)
  • Tree with bring-to-top. Supposed to be nice for caches.
    Skip List Wikipedia Not really either, but externally resembles a tree. pyskip A list of lists that acts like a tree.
    Red-Black Tree Wikipedia Tree RBTree.py (red-black tree) Red-Black tree. Supposed to be slower than a treap, but less variable.
    AA Tree Wikipedia Tree aatree A simplified form of Red-Black tree.
    AVL Tree Wikipedia Tree bintrees
    2-3 Tree Wikipedia Tree 2-3 tree
    B Tree Wikipedia Tree
  • Larch
  • btree.BTree (also has a B+ Tree)
  • B+ Tree Wikipedia Tree
  • btree.BPlusTree (also has a B Tree)
  • sorteddict
  • SQLite3
  • mxBeeBase
  • Tango Tree Wikipedia Tree None? Primarily interesting for theoretical reasons? Does lookups in O(log(log(n))) time, but does not support insertions or deletions.
    Binary Heap Wikipedia Heap heapq (in the PSL) A traditional heap in a list (array).
    Binomial Heap Wikipedia Heap Binomial Queues (Python recipe) Mergeable. Read/write.
    Fibonacci Heap Wikipedia Heap Alistair Rendell's Theoretically interesting because many operations are O(1).
    Pairing Heap Wikipedia Heap Two pass variant Relatively simple implementation and excellent practical amortized performance.
    Brodal Queue Stackoverflow Heap (?) None? Theoretically interesting, but in the words of Brodal himself, "quite complicated" and "[not] applicable in practice."