Zeyuan Allen Zhu: Disjoint-Set Unions

I think the algorithm that surprised me the most in my lifetime is the disjoint union data structure. Perhaps because I was too young (10 years ago, at age of 13), but definitely that was my first time seeing an amortized complexity bound, and in addition to it, if you only do path compression the complexity seems to be log* but if you add it with union-by-rank it decreases to inverse Ackermann. From a practical perspective, doing path compression is enough… So amazing, isn’t it?