Skip lists! Super wacky, super fun to implement. O(log n) insertion/deletion/binary search, maintained sorted. It's probabilistic; you have a number of linked list levels, so you flip k coins to insert a node, and insert into the lowest k linked lists.

also, radix heaps are underappreciated.