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 | 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 | ||

B+ Tree | Wikipedia | Tree | ||

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." |