Datastructure	Hide column Theory	Hide column Tree or Heap?	Hide column Python Implementations	Hide column Notes
Hide rowTreap	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.
Hide rowSplay Tree	Wikipedia	Tree	splay_mod pysplay (above entry was derived from this one?)	Tree with bring-to-top. Supposed to be nice for caches.
Hide rowSkip List	Wikipedia	Not really either, but externally resembles a tree.	pyskip	A list of lists that acts like a tree.
Hide rowRed-Black Tree	Wikipedia	Tree	RBTree.py (red-black tree)	Red-Black tree. Supposed to be slower than a treap, but less variable.
Hide rowAA Tree	Wikipedia	Tree	aatree	A simplified form of Red-Black tree.
Hide rowAVL Tree	Wikipedia	Tree	bintrees
Hide row2-3 Tree	Wikipedia	Tree	2-3 tree
Hide rowB Tree	Wikipedia	Tree	Larch btree.BTree (also has a B+ Tree)
Hide rowB+ Tree	Wikipedia	Tree	btree.BPlusTree (also has a B Tree) sorteddict SQLite3 mxBeeBase
Hide rowTango Tree	Wikipedia	Tree	None?	Primarily interesting for theoretical reasons? Does lookups in O(log(log(n))) time, but does not support insertions or deletions.
Hide rowBinary Heap	Wikipedia	Heap	heapq (in the PSL)	A traditional heap in a list (array).
Hide rowBinomial Heap	Wikipedia	Heap	Binomial Queues (Python recipe)	Mergeable. Read/write.
Hide rowFibonacci Heap	Wikipedia	Heap	Alistair Rendell's	Theoretically interesting because many operations are O(1).
Hide rowPairing Heap	Wikipedia	Heap	Two pass variant	Relatively simple implementation and excellent practical amortized performance.
Hide rowBrodal Queue	Stackoverflow	Heap (?)	None?	Theoretically interesting, but in the words of Brodal himself, "quite complicated" and "[not] applicable in practice."