Skip to content

Zeyuan Allen Zhu: Disjoint-Set Unions

by on February 19, 2012

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?

Advertisements
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: